Verification of normality of linear operator Let $X = (1,1,0),(1,-1,0),(0,0,1)$ be the basis of unitary space $\mathbb{C}^3$. Let $A$ be a linear operator, and $\mathbb{A}$ it's matrix in basis $X$: 
$$ \mathbb{A} = \begin{pmatrix}3 & i & 0\\
-i & 3 & 0\\
0 & 0 & 4
\end{pmatrix} $$
Verify that $A$ is normal and find an orthonormal basis in which $A$ is diagonal.
On the first look, the operator is obviously hermitian, because it's matrix is hermitian. Hermitian operators are normal and thus orthogonally diagonalizable.
However, there's  a theorem saying that $A$ is a normal operator if and only if it's matrix in some orthonormal basis is a normal matrix. In this case $X$ is not orthonormal basis, only orthogonal. 
Is the observation of $A$ being hermitian incorrect then? I noticed that if I orthonormalize $X$ and transform $\mathbb{A}$ or transform $\mathbb{A}$ into standard basis (which is orthonormal under standard dot product) the hermitian property doesn't change.
Do I explicitly need to always convert to orthonormal basis to verify the normality, or are there some exceptions where the orthogonal is "sufficient"? What is the correct justification?
 A: To avoid confusion, I will call your linear operator $T$ instead of $A$.
Let $D=\operatorname{diag}(\|x_1\|,\ldots,\|x_n\|)$. Then the orthonormal basis corresponding to the basis vectors in $X$ are given by the vectors in $XD^{-1}$. If the matrix of a linear operator $T$ w.r.t. the standard basis is $M$, then $\mathbb{A}=X^{-1}MX$ and the matrix of $T$ w.r.t. the (orthonormal) basis vectors in $XD$ is given by $(XD^{-1})^{-1}M(XD^{-1}) = D\mathbb{A}D^{-1}$.
Now the answer to your first question is both yes and no. No, in general, that $\mathbb{A}$ is normal (resp. Hermitian) does not necessarily imply that $D\mathbb{A}D^{-1}$ is also normal (resp. Hermitian). But yes, in your particular case, it happens that $D\mathbb{A}D^{-1}=\mathbb{A}$ (I'll leave the proof to you). So, the matrix of $T$ w.r.t. the orthonormal basis from $XD^{-1}$ is Hermitian. Therefore, $T$ is a normal operator.
At any rate, to show that $T$ is normal, you may prove that $M$ (the matrix of $T$ w.r.t the standard basis) or $D\mathbb{A}D^{-1}$ (the matrix of $T$ w.r.t. a orthonormal basis) is normal. In principle, showing that $\mathbb{A}$ is a normal matrix is irrelevant.
A: In general, let $A$ be an operator on a finite-dimensional inner product space $V$, and let $\beta = \{v_1,\dotsc,v_n\}$ be an orthogonal basis of $V$. Then
$$
 A v_k = \sum_{j=1}^n \frac{\langle v_j, A v_k\rangle}{\|v_j\|^2} v_j,
$$
so that the matrix $[A]_\beta$ of $A$ with respect to $\beta$ is given by
$$
 ([A]_\beta)_{jk} = \frac{\langle v_j, A v_k\rangle}{\|v_j\|^2}.
$$
Hence, $[A^\ast]_\beta$ is given by
$$
 ([A^\ast]_\beta)_{jk} = \frac{\langle v_j, A^\ast v_k\rangle}{\|v_j\|^2} = \frac{\langle A v_j,  v_k\rangle}{\|v_j\|^2} = \frac{\|v_k\|^2}{\|v_j\|^2} \frac{\overline{\langle v_k,  A v_j\rangle}}{\|v_k\|^2} = \frac{\|v_k\|^2}{\|v_j\|^2} \overline{([A]_\beta)_{kj}},
$$
so that
$$
 [A^\ast]_\beta = \Delta^{-1} ([A]_\beta)^\ast \Delta, \quad \Delta := \operatorname{diag}(\|v_1\|,\dotsc,\|v_n\|);
$$
the matrix $\Delta$ precisely accounts for the failure of $\beta$ to be orthonormal. 
Thus, $A$ is normal if and only if $A A^\ast = A^\ast A$, if and only if $[A]_\beta [A^\ast]_\beta = [A^\ast]_\beta [A]_\beta$, if and only if
$$
 [A]_\beta \Delta^{-1} ([A]_\beta)^\ast \Delta = \Delta^{-1}([A]_\beta)^\ast \Delta [A]_\beta;
$$
it is just a coincidence that in your example, $A_\beta = \mathbb{A}$ commutes with $\Delta$, and hence $$[A^\ast]_\beta = \Delta^{-1} ([A]_\beta)^\ast \Delta = ([A]_\beta)^\ast.$$
