Your statement is basically true for the conventional Hilbert space without spin or other bells and whistles. I don't wish to get into proofs, as flakey proofs are an excuse to miss the point in such contexts, more often than not, and reduce the issue to their assumptions, better sheltered from your inquisitiveness.
You may appreciate this is true and natural in QM in finite-dimensional spaces, as Weyl nicely illustrates in his book, using Sylvester's clock and shift matrices, which provide a complete, orthogonal basis of $GL(N,\mathbb{C})$. The careful $N\to \infty$ limit of this construction amounts to your statement.
In actual practice, the Wigner-Weyl transform maps phase-space functions to Hilbert space operators invertibly, and any other ordering prescription (like your "normal" ordering, with momenta on the right), is formally equivalent to Weyl ordering, and so can be systematically converted to it.
Crudely, all phase-space functions are expandible in such polynomials, and their Weyl transforms are perfectly symmetrized polynomials in $\hat x$ and $\hat p$, as detailed in phase-space quantum mechanics books, like this one. you may normal order those to your reference expression. If you had a fetish for rigor, you might try Wong's book, which is clearly overkill. Learning how to use the formalism correctly for routine problems, instead, should assuage your anxieties.
People have objected to your expansion which excludes functions non analytic at the origin, but I'll give you a well-meaning extension of it, such as "a sensible function of $\hat x$ and $\hat p$" : I am assuming you are not fussing about analyticity and such, which you may always fix by smoothing of sorts in practice.
- Geeky Aside on specific question that arose in a linked question.
The question arose there how an integral operator such as
$$ A_x \psi(x) = \int\!\!dy~ K(x,y) \psi(y) $$
is represented as a function of $\hat x$ and $\hat p$.
Observe
$$ \int\!\!dy~ K(x,y) \psi(y)= \int\!\!dy~ K(x,y+x) \psi(y+x)\\
= \int\!\!dy~ K(x,y+x)~e^{y\partial_x} \psi(x), $$
hence
$$ \hat A =\int\!\! dy~ K(\hat x, y+\hat x)~ e^{iy\hat p/\hbar},
$$
with self-evident matrix elements.