It suffices to show that for some unitary matrix $W$, $AW$ is normal, i.e. $(AW)^*(AW)=(AW)(AW)^*$ where $*$ denotes conjugate-transpose. By the spectral theorem (see the linked wikipedia article), we can then write $D=U^{-1}A(WU)$ for some unitary $U$ and diagonal $D$.
The condition $(AW)^*(AW)=(AW)(AW)^*$ simplifies to $W^*A^*AW=AA^*$ since $WW^*=I$. Since $A^*A$ and $AA^*$ are Hermitian, by the spectral theorem they can be diagonalized by unitary matrices, so we have $X^*A^*AX=D$ and $Y^*AA^*Y=D'$ for some unitary $X,Y$ and diagonal $D,D'$. But the entries of $D$ and $D'$ are the eigenvalues of $A^*A$ and $AA^*$, and it is well-known that the eigenvalues of $AB$ and $BA$ coincide for any square matrices $A,B$. Thus $D=D'$ so $X^*A^*AX=Y^*AA^*Y$. Letting $W=XY^*$ which is unitary we get $W^*A^*AW=AA^*=Y(X^*A^*AX)Y^*=AA^*$ as desired.