Let $\phi$ be an automorphism of $M_2({\mathbb C})$. Put $F_{ij}=\phi(E_{ij})$. We have the identity $E_{ij}E_{kl}=\delta_{jk}E_{il}$, where $\delta_{jk}$ is the Kronecker symbol. So $F_{ij}F_{kl}=\delta_{jk}F_{il}$. In particular, $F_{ii}^2=F_{ii}$ for any $i$. So $F_{11}$ and $F_{22}$ are projectors. Also, $F_{11}F_{22}=F_{22}F_{11}=0$.
I claim that ${\sf Im}(F_{11}) \cap {\sf Im}(F_{22})=\lbrace 0 \rbrace$. Indeed, let $a\in {\sf Im}(F_{11}) \cap {\sf Im}(F_{22})$. Then we have $x_1,x_2$ such that $a=F_{11}x_1=F_{22}x_2$. Then $a=F_{11}a=F_{11}F_{22}x_2=0x_2=0$ as claimed.
Also, $E_{11}+E_{22}=I_2$ yields $F_{11}+F_{22}=I_2$. So any $a\in {\mathbb C}^2$ can be written $a=F_{11}a+F_{22}a \in {\sf Im}(F_{11}) + {\sf Im}(F_{22})$. So we see that ${\mathbb C}^2$ is the direct sum $ {\mathbb C}^2={\sf Im}(F_{11}) \oplus {\sf Im}(F_{22}) \tag{1}$
Since $\phi$ is an automorphism, its kernel is trivial, so $F_{11}\neq 0$ and $F_{22} \neq 0$. So the summand spaces in (1) are not zero, and the only possibility is that they have both dimension $1$. So there are independent vectors $v_1,v_2$ such that ${\sf Im}(F_{11})={\sf Vect}(v_1)$ and ${\sf Im}(F_{22})={\sf Vect}(v_2)$.
For each $i$, $F_{ii}(v_i)$ is in ${\sf Im}(F_{ii})={\sf Vect}(v_i)$ so there is a $\lambda$ such that $F_{ii}(v_i)=\lambda v_i$. From $F_{ii}^2=F_{ii}$, we deduce $\lambda^2=\lambda$. As clearly $\lambda \neq 0$, we have $\lambda=1$, so
$ F_{11}(v_1)=v_1, F_{22}(v_2)=v_2 \tag{2} $
Then
$ F_{11}v_2=F_{11}\bigg(F_{22}v_2\bigg)=0v_2=0 \tag{3} $ and similarly $F_{22}v_1=0$. Further,
$ F_{12}v_1=F_{12}\bigg( F_{11}v_1 \bigg)=0v_1=0 \tag{4} $
Also, $F_{12}v_2=F_{11}F_{12}v_2 \in {\sf Im}(F_{11})$, so there is a constant $\lambda$ such that $F_{12}v_2=\lambda v_1$. Similarly, there is a constant $\mu$ such that $F_{21}v_1=\mu v_2$. Then, $v_1=F_{11}v_1=F_{12}F_{21}v_1=(\lambda \mu)v_1$, so $\mu=\frac{1}{\lambda}$.
Let $A$ be the unique matrix satisfying $A(e_1)=\lambda v_1$ and $A(e_2)=v_2$. Then $\phi(X)=A^{-1}XA$ for any $X$, qed.