Does $\langle Fv_j, Fv_j \rangle = \langle F^*v_j, F^*v_j \rangle$ imply that $F$ is normal? 
Let $\{v_1, \ldots, v_n\}$ be an orthonormal basis of an inner product space $V$ and a linear $F:V\to V$ s.t. for all $j$: $$\langle Fv_j, Fv_j \rangle =  \langle F^*v_j, F^*v_j \rangle.$$ Does it imply that $F$ is normal?

At first, I thought that we just need to set $T:=F^*F-FF^*$ and then $\langle Tv_j, v_j \rangle=0$ would imply that $T=0$ but it doesn't (any non-zero matrix with zeros on the diagonal is a counterexample).
It looks like the problem boils down to

Let $A^*A-AA^*$ have zeros on the diagonal. Does $A^*A=AA^*$ hold?

 A: Let $F=\begin{bmatrix} 0 & 1 \\ 0 & 0\end{bmatrix}$. It
is easy to see that $F$ is not normal. Then
$F^*F-F F^* = \begin{bmatrix} -1 & 0 \\ 0 & 1\end{bmatrix}$.
Let $v_1 = {1 \over \sqrt{2}}(1,1)^T, v_2 ={1 \over \sqrt{2}} (1,-1)^T$. These are orthonormal and 
$\langle v_k ,(F^*F-F F^*)v_k \rangle = 0$ for $k=1,2$.
A: I believe it is false.
Let 
$$F = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & \sqrt2 \\ 1 & 1 & 0 \end{pmatrix}$$
and let $v_j$ be the standard basis.
Then, you can check
$$FF^* = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 2 \end{pmatrix}; \quad F^*F = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 2 & 0 \\ 0 & 0 & 2 \end{pmatrix}$$
so that $F$ is not normal, and on the other hand:
$$
Fv_1 = \begin{pmatrix} 0 \\ 0 \\ 1\end{pmatrix}; \quad F^*v_1 = \begin{pmatrix} 0 \\ 1 \\ 0\end{pmatrix} \\
Fv_2 = \begin{pmatrix} 1 \\ 0 \\ 1\end{pmatrix}; \quad F^*v_2 = \begin{pmatrix} 0 \\ 0 \\ \sqrt2\end{pmatrix} \\
Fv_3 = \begin{pmatrix} 0 \\ \sqrt2 \\ 0\end{pmatrix}; \quad F^*v_3 = \begin{pmatrix} 1 \\ 1 \\ 0\end{pmatrix}
$$
which pairwise all have the same length.
Note: to cook up this counterexample, I started by writing down a general $2\times 2$ matrix (i.e. with entries $a,b,c,d$) and took the standard basis to see what conditions would be imposed on $a,b,c,d$. In this case, it's just $b^2 = c^2$ which will yield a symmetric or anti-symmetric (and thus normal) matrix.
So, moving to a $3\times 3$ matrix, and only focusing on the off-diagonal (as you note, the diagonal basically "isn't in play" here) to come up with conditions on the remaining $6$ entries. Start out easy, choose one of them to be $1$, the next to be $0$, and then start choosing other coefficients to avoid symmetry/anti-symmetry. Choosing other entries equal to $1$ or $0$ yielded a normal matrix, that is when I had the idea to switch in a $\sqrt 2$.
