A traceless matrix has a zero diagonal in some orthonormal basis

Step 1: a unit vector with $x^TAx=0$. Let $S=\frac{A+A^T}2$; $\operatorname{tr}S=\operatorname{tr}A=0$. Its eigenvalues $\lambda_1\le\dots\le\lambda_n$ have sum $0$, so $\lambda_1\le0\le\lambda_n$. By the numerical range theorem (previous problem, $n\ge2$) $\{x^TAx:|x|=1\}=[\lambda_1,\lambda_n]\ni0$. So there is a unit $x_1$ with $x_1^TAx_1=0$. (For $n=1$, $A=(0)$ and any unit vector works.)

Step 2: induction. Extend $x_1$ to an orthonormal basis and let $W=x_1^\perp$ (dimension $n-1$), with an orthonormal basis forming the columns of an $n\times(n-1)$ matrix $B$. The compression $A'=B^TAB\in M_{n-1}(\mathbb{R})$ has
$$\operatorname{tr}A'=\operatorname{tr}A-x_1^TAx_1=0-0=0,$$
since the trace in the orthonormal basis $(x_1,\text{columns of }B)$ is the sum of the diagonal entries $x_1^TAx_1+\operatorname{tr}A'$.

By the induction hypothesis there is an orthonormal basis $(g_2,\dots,g_n)$ of $W$ in which $A'$ has zero diagonal, i.e. $g_i^TAg_i=0$ (for $g_i\in W$, $g_i^TA g_i$ is exactly the corresponding diagonal entry of the compression).

Conclusion. $(x_1,g_2,\dots,g_n)$ is an orthonormal basis of $\mathbb{R}^n$ with all $f_i^TAf_i=0$.

Example. $A=\operatorname{diag}(1,-1)$: $x=\frac1{\sqrt2}(1,1)$ gives $x^TAx=0$, and $\frac1{\sqrt2}(1,-1)$ also; in this basis $A=\begin{pmatrix}0&1\\1&0\end{pmatrix}$.

Remark. Conversely a matrix with zero diagonal in an orthonormal basis has trace zero, so $\operatorname{tr}A=0$ iff $A$ is orthogonally similar to a zero-diagonal matrix. The same statement holds with "similar" in place of "orthogonally similar" (trivially, with a basis that is not orthonormal) and it is the matrix version of: a trace-zero matrix is a sum of commutators (Albert-Muckenhoupt).