New proof about normal matrix is diagonalizable.
This Wikipedia article contains a sketch of a proof. It has three steps.
If a normal matrix is upper triangular, then it's diagonal. (Proof: show the upper left corner is the only nonzero entry in that row/column using a matrix-norm argument; then use induction.)
Details of proof: write $A$ as $Q T Q^{-1}$ for some unitary matrix Q, where $T$ is upper triangular. From $A A^{*} = A^{*} A$, conclude that $T T^{*} = T^{*} T$. Observe that the left hand side is the matrix whose $ij$ entry is $\langle t_i, t_j\rangle$, where $t_i$ is the $i$th column of $T$. The right hand side has an $ij$ entry that's $\langle s_i, s_j\rangle$, where $s_i$ is the $i$ the row.
Considering $i = 1$, you can conclude that the norm of the first row is the same as the norm of the first column, so all the non-diagonal entries of that row must be zero. Now look at the $(2,2)$ entries of the two matrices: the second column has the form $(0, t_{2,2}, 0, \ldots, 0)$; the second row may have nonzero entries after the second. But the norms of these two vectors must be equal, so all those potentially nonzero entries must be zero. Continue in this vein until you've shown that all off-diagonal entries are zero.
Show that every matrix is (unitarily) similar to an upper triangular one [that's called the Schur Decomposition], and that the similarity doesn't change "normality": if $A$ is similar to upper-triangular $T$, and $A$ is normal, then so is $T$.
Conclude that a normal matrix is similar to an upper-triangular normal matrix, which is necessarily diagonal, by step 1, so you're done.
I know that's not the proof you asked for, but as @lhf points out, your proposed proof goes via a route that doesn't require normality, so it can't possibly work.
When $X$ is a unitary space, and $A:\>X\to X$ is a normal operator then one has $$\|Ax-\lambda x\|^2=\|A^*x-\bar\lambda x\|^2\qquad\forall x\in X,\ \forall\lambda\in{\mathbb C}\ .$$ It follows that $Ax=\lambda x$ implies $A^*x=\bar\lambda x$; whence $A$ and $A^*$ have the same eigenvectors.
By the fundamental theorem of algebra $A$ has an eigenvalue $\lambda\in C$ and a corresponding eigenvector $e\ne0$. Put $U:=\langle e\rangle^\perp$. When $x\in U$ then $$\langle Ax,e\rangle=\langle x,A^*e\rangle=\langle x,\bar\lambda e\rangle=0\ ,$$ whence $Ax\in U$. In a similar way one shows that $A^*x\in U$ as well.
It follows that $A\restriction U$ is a normal operator on $U$. This observation allows to set up an induction proof of your claim.
As you told, $$A^*A=U^*DU$$ for some unitary matrix $U$, and $D$ a diagonal matrix. Since $AA^*=A^*A$, we have: $$(U^*DU)A=AA^*A=A(U^*DU).$$Consider LHS and RHS of this equation, we multiply $U$ on the left, $U^*$ on the right and get: $$D(UAU^*)=(UAU^*)D.$$Now the matrix $UAU^*$ is interchangable with a diagonal matrix.
If the diagonal entries of $D$ are mutually distinct, then it is easy to show that $UAU^*$ is diagonal as well. Hence we just need to consider the case when $D=\lambda I$. In this case we have $$A^*A=U^*(\lambda I)U=\lambda I.$$Let $v$ be an eigenvector of $A$ with respect to an eigenvalue $\mu$. Then \begin{align} v^*A^*Av=\bar{\mu}v^*\mu v=|\mu|^2|v|^2\\ v^*A^*Av=v^*(\lambda I)v=\lambda|v|^2 \end{align} Comparing these two equations we get $\lambda=|\mu|^2$. So the matrix $\frac{1}{\mu}A$ is a unitary matrix. Moreover, we know unitary matrices are diagonalizable, so we are done.
$\textbf{Note: }$Maybe this is somewhat the proof you asked for. However, I am afraid this is not particularly easier than the one of @Joh Hughes.