Fast 128-bit MAC with second preimage resistance?
I really like this question, and have two things to say.

First note that CBC-MAC is no good since given the key it's easy to find a collision. Let $t$ be a tag for a message $m=m_1,m_2$ of length $\ell$ bits. Then, in CBC-MAC the input to AES first is $\ell$ and then the output is XORed with $m_1$ and input to AES, and so on. Let $t_1$ be the intermediate value output from AES with $m_1$. Then, you can make any change to $m_1$ and compute $t_1'$. Now take $m_2'$ so that $m_2'\oplus t_1' = m_2 \oplus t_1$. This will give you the same output tag $t$. (I hope that this is clear.)

Now, let's try and answer better. Specifically, let's assume that there exists a construction that gives what you want, and so you have collision resistance even given the key. This actually gives you a construction of a hash function from a block cipher. We have some such constructions in the ideal cipher model, like Davies-Meyer. However, these are problematic to apply to AES since AES has weaknesses under related key attacks (which are exactly the types of attacks that appear when constructing a hash function from a block cipher).

Based on @otus's comment, I will extend my answer to deal with theory as well. What you are really asking is to build a second-preimage resistant hash function from a block cipher. Practically, we don't know how to do this differently to full collision resistance (to the best of my knowledge; please correct me if I'm wrong). However, theoretically, it is possible to construct universal one-way hash functions (which are second preimage-resistant hash functions) from one-way functions. This is a famed result by Rompel, with a full proof here. Thus, theoretically speaking, it is possible to construct such a hash function from block ciphers (since block ciphers are pseudorandom permutations and one-way functions can easily be constructed from them).

In contrast, Simon proved that collision-resistant hash functions cannot be constructed from one-way functions in a black-box way.