$\mathbf{A}^T = p(\mathbf{A})$, prove that $\mathbf{A}$ is invertible

Your proof for part 1 is perfect.

For part 2, I assume that the question should be as follows:

Is it true that for every operator $\phi: \mathbb{R}^n\rightarrow\mathbb{R}^n$, there exists some polynomial $p(x)$ and a basis for which the matrix of $\phi$ relative to this basis satisfies the condition of $A^\top = p(A)$?

First, to correct the answer you gave, it is not true that normality is independent of the basis chosen: If you apply a non-unitary change of basis to a normal matrix, then the resulting matrix might not be normal. For instance, note that if we take $$ A = \pmatrix{0&2\\2&0}, \quad S = \pmatrix{2&0\\0&1}, $$ then $A$ is normal but $SAS^{-1}$ is not.

One way to answer the question is to give an example of an operator for which the condition cannot hold. Consider in particular the operator $\phi(x) = Mx$ with $$ M = \pmatrix{0&1\\0&0}. $$ $\phi$ fails to be diagonalizable and therefore cannot be normal relative to any choice of basis. Thus, it cannot be the case that the matrix $A$ of $\phi$ satisfies $A^\top = p(A)$.