Since $U$ is unitary, $U^*=U^{-1}$. So, let us first think about how to find a matrix $U$ such that $U^{-1}AU$ is diagonal, without worrying about the condition that $U$ be unitary; we'll come back to fix that detail at the end.
Think about it this way: to diagonalize $A$, you want to find a change of basis: we know that the matrix for this transformation with respect to the basis $\{V_1,V_2\}$ is
$$
\begin{pmatrix}3 & 0\\0 & 0\end{pmatrix},
$$
because it maps $V_1$ to $3V_1$ and $V_2$ to $0V_2$.
If $U^{-1}AU$ is going to give you this, we want it to work like like so: when we plug in the vector $(1,0)^{T}$, we want $U$ to transform that in to $V_1$, so that $AU$ transforms it in to $3V_1$, so that $U^{-1}AU$ transforms it in to $(3,0)^T$. Does that make sense?
If $U$ is going to transform $(1,0)^T$ in to $V_1$, then the first column of $U$ must be exactly $V_1$. Similarly, the second column must be $V_2$. So, by this logic, we should take
$$
U=\begin{pmatrix}1+i & -1-i\\2 & 1\end{pmatrix}.
$$
For this matrix $U$, we certainly have $U^{-1}AU$ being the above matrix. However, there's one problem here: this matrix is not unitary.
So, instead of using $V_1$ and $V_2$ directly, let's use $W_1=\frac{V_1}{\|V_1\|}$ and $W_2=\frac{V_2}{\|V_2\|}$. If you take the matrix $U$ whose first column is $W_1$ and second column is $W_2$, you should get the properties you want.
In this case, we have
$$
\|V_1\|=\sqrt{(1+i)(1-i)+2^2}=\sqrt{6}\qquad \|V_2\|=\sqrt{(-1-i)(-1+i)+1^2}=\sqrt{3}
$$
and so we would take
$$
U=\begin{pmatrix}\frac{1+i}{\sqrt{6}} & \frac{-1-i}{\sqrt{3}}\\\frac{2}{\sqrt{6}} & \frac{1}{\sqrt{3}}\end{pmatrix}
$$
You can check that in this case, $U^*=U^{-1}$.
Best Answer
An explicit construction for the general case is probably not worth the trouble. However, the explicit construction for the $n = 2$ case is simple enough. I assume that $\lambda_1 \neq \lambda_2$; if the eigenvalues are equal, there is no real "permutation" to make and we could simple choose $U = I$.
As in the proof of Schur's theorem, we note that the first column of $U$ should be an eigenvalue of $A$ associated with $\lambda_2$. Note that $$ A - \lambda_2 I = \pmatrix{\lambda_1 - \lambda_2 & x\\ 0 & 0}. $$ We can see that one eigenvector associated with $\lambda_2$ is given by $$ v = (x, \lambda_2 - \lambda_1). $$ In order to make this a column of $U$, this vector must be normalized. Accordingly, we can take the first column of $U$ to be $ u_1 = v/\|v\|. $ With that, we have $$ u_{11} = x/\sqrt{|x|^2 + |\lambda_1 - \lambda_2|^2}, \quad u_{21} = (\lambda_2 - \lambda_1)/\sqrt{|x|^2 + |\lambda_1 - \lambda_2|^2}. $$ From there, the second column must be a unit vector orthogonal to the first column. So, there must be an $\alpha \in \Bbb C$ with $|\alpha| = 1$ such that $$ u_{12} = \alpha (\overline{\lambda_1 - \lambda_2})/\sqrt{|x|^2 + |\lambda_1 - \lambda_2|^2} = -\alpha \bar u_{21}, \\ u_{22} = \alpha \bar x /\sqrt{|x|^2 + |\lambda_1 - \lambda_2|^2} = \alpha \bar u_{22}. $$ In order to find a suitable value of $\alpha$, note that the $1,2$ entry of $U^*AU$ is given by $$ x = \pmatrix{\bar u_{11} & \bar u_{21}} A \pmatrix{u_{12}\\ u_{22}} = \\ \alpha \cdot \pmatrix{\bar u_{11} & \bar u_{12}} A \pmatrix{-\bar u_{21}\\\bar u_{11}} =\\ \alpha \cdot \frac{1}{|x|^2 + |\lambda_1 - \lambda_2|^2} \cdot \pmatrix{\bar x & \overline{\lambda_2 - \lambda_1}} A \pmatrix{\overline{\lambda_1 - \lambda_2}\\\bar x}. $$ In other words, if $x$ is non-zero, then $\alpha$ must be taken to be $\alpha = e^{-i \theta}$, where $\theta$ is the argument of the number $$ \frac{1}{x(|x|^2 + |\lambda_1 - \lambda_2|^2)} \cdot \pmatrix{\bar x & \overline{\lambda_2 - \lambda_1}} A \pmatrix{\overline{\lambda_1 - \lambda_2}\\\bar x}. $$