All polynomials are the sum of three others, each of which has only real roots

Every real polynomial $f$ is the sum of TWO polynomials $g,h$ with all zeros real (of the same degree). Indeed, take any $g_1$ of the same degree as $f$, whose roots are real and simple. Small perturbation does not destroy this property. Therefore $h_1=g_1+\epsilon f$ also has real zeros when $\epsilon$ is small and real. Now take $g=-g_1/\epsilon, \; h=h_1/\epsilon$. We obtain $f=g+h$, and both $g,h$ have real zeros.

A stronger result is available: Every real entire function $f$ of exponential type and satisfying $$\int_{-\infty}^\infty\frac{\log|f(x)|}{1+x^2}dx<\infty$$ (evidently this class contains all real polynomials) is a sum of two entire functions of the same exponential type with all zeros real (and moreover, with all $\pm1$ points real).

Your conjecture is not a formal corollary from this result, because it does not say that the summands are polynomials if $f$ is a polynomial, but if you look at the proof you see that when applied to a polynomial it gives polynomials of the same degree (the general idea of the proof is the same as in my proof in the first paragraph).

The reference is MR0751391 Katsnelʹson, V. È. On the theory of entire functions of the Cartwright class. (Russian) Teor. Funktsiĭ Funktsional. Anal. i Prilozhen. No. 42 (1984), 57–62. English transl: MR0862002 American Mathematical Society Translations, Series 2, Vol. 131. Ten papers in analysis. AMS Translations, Ser. 2, 131.American Mathematical Society, Providence, RI, 1986. viii+120 pp. ISBN: 0-8218-3106-2

Remark 1. There is a lot of arbitrary choice in the construction in the first paragraph. One reasonable choice of $g_1$ would be the Chebyshev polynomial of degree $d=\mathrm{deg}\, f$. It has $d+1$ points of alternance, where the critical values are $\pm1$. So if we take $\epsilon<1/\| f\|,$ where $\| f\|$ is the $\sup$-norm on $[-1,1]$, then the construction works, because $g_1+\epsilon f$ has at least $d$ sign changes on $[0,1]$ thus all roots are real. So the coefficients of $g$ and $h$ can be estimated in terms of $\| f\|$ or in terms of the sup-norm on any interval. One can probably state and solve some extremal problem about this.

Remark 2. In the original problem (see the reference on BAMS in the question), $f$ is a Hurwitz polynomial (zeros in the left-half-plane), and it is required that $g,h$ be also Hurwitz. This can be easily achieved even without the condition that $f$ is Hurwitz. Indeed, the argument in Remark 1 yields $g,h$ whose zeros lie on an arbitrary prescribed interval.

To address the original question about the polynomials with complex coefficients.

Given a polynomial $P\in\mathbb C[x]$ of degree $n$, write $P=Q+iR$ with $Q,R\in\mathbb R[x]$, and fix arbitrarily a polynomial $S\in\mathbb R[x]$ of degree $n$ with all roots real and pairwise distinct. As observed in Eremenko's answer, for any $\varepsilon\ne 0$ sufficiently small in absolute value, the polynomials $Q_\varepsilon:=S+\varepsilon Q$ and $R_\varepsilon:=S+\varepsilon R$ will also have all their roots real, and then \begin{align*} P &= Q+iR \\ &= \varepsilon^{-1}(Q_\varepsilon-S)+i\varepsilon^{-1}(R_\varepsilon-S) \\ &= \varepsilon^{-1}Q_\varepsilon+i\varepsilon^{-1}R_\varepsilon-(1+i)\varepsilon^{-1}S \end{align*} is the required representation of $P$ as a sum of three polynomials of degree at most $n$ with all their roots real.

This is the answer only to my own question in the comments.

Two polynomials with real roots are not enough in general.

For seeing this, assume that $f(z)=\lambda g(z)+\mu h(z)$ for complex numbers $\lambda$, $\mu$ and real polynomials $g,h$. Then $\bar{f}=\bar{\lambda}g+\bar{\mu}h$, and provided that $f/\bar{f}\ne \rm{const}$, we solve this $2\times 2$ system for $g, h$ and see that $g$ is a linear combination of $f,\bar{f}$. In other words, $g$ is a real linear combination of $\operatorname{Re}f, \operatorname{Im}f$. But it often happens that no real linear combination of two given real polynomials has only real roots. Indeed, take the polynomials like $x^{100}+1$ and $x^{17}+x^5$, by sign change (Descartes?) estimate their linear combination can not have only real roots.