Is every skew-adjoint matrix a commutator of two self-adjoint matrices

Yes, self adjoint solutions always exist.

Since $A$ is skew Hermitian and traceless, it is unitarily similar to some skew Hermitian matrix with zero diagonal (the proof is deferred to the end of this answer). So, WLOG, we may assume that $A$ has a zero diagonal. We now take $X$ as an arbitrary diagonal matrix $\mathrm{diag}(x_1,\ldots,x_n)$ with real and distinct diagonal entries. The equation $A=XY-YX$ then boils down to $(x_i-x_j)y_{ij} = a_{ij}$, which is solvable as $y_{ij}=a_{ij}/(x_i-x_j)$.

Finally, we show that $A$ is unitarily similar to a skew Hermitian matrix with zero diagonal. Firstly, unitarily diagonalize $A$ to a purely imaginary diagonal matrix $D$. Let $U$ be a unitary matrix with $\frac{1}{\sqrt{n}}(1,1,\ldots,1)$ as its last row. Then the $(n,n)$-th entry of $\tilde{A}=UDU^\ast$ is a multiple of the sum of all entries of $D$, which is zero by assumption. Do the similar for the leading principal $(n-1)\times(n-1)$ submatrix of $\tilde{A}$, and continue in this manner recursively, we get a skew Hermitian matrix with zero diagonal.

Edit: On a second thought, actually every real (resp. complex) matrix with zero trace is similar to a matrix with zero diagonal. Hence the above idea of directly solving $Y$ can be employed to show that every real (resp. complex) matrix with trace zero is the commutator of two real (resp. complex) matrices. Consequently, we have an elementary proof that the set of matrix commutators over $\mathbb{R}$ or $\mathbb{C}$ form a matrix subspace (which is the space of all matrices with zero trace).