The following algorithm suggests itself. Let $\alpha$ be an unknown root of a polynomial $f(x)$ of degree $n$, and $\beta$ be an unknown root of a polynomial $g(x)$ of degree $m$.
Using the equation $f(\alpha)=0$ allows us to rewrite any power $\alpha^k$ as
a linear combination of $1,\alpha,\alpha^2,\ldots,\alpha^{n-1}$. Similarly using the equation $g(\beta)=0$ allows us to rewrite any power $\beta^\ell$ as a linear
combination of $1,\beta,\beta^2,\ldots,\beta^{m-1}$. Putting these two pieces together shows that we can write any monomial $\alpha^k\beta^\ell$ as a linear combination of the $mn$ quantities $\alpha^i\beta^j, 0\le i<n, 0\le j<m.$
Denote $c_k=\alpha^i\beta^j$, where $k=mi+j$ ranges from $0$ to $mn-1$.
Next let us use the expansions of $(\alpha\beta)^t$, $0\le t\le mn$ in terms of the $c_k$:s. Let these be
$$
(\alpha\beta)^t=\sum_{k=0}^{mn-1}a_{kt}c_k.
$$
Here the coefficients $a_{tk}$ are integers. We seek to find integers $x_t,t=0,1,\ldots,mn$, such that
$$
\sum_{t=0}^{mn}x_t(\alpha\beta)^t=0.\qquad(*)
$$
Let us substitute our formula for the power $(\alpha\beta)^t$ above. The equation $(*)$ becomes
$$
0=\sum_t\sum_kx_ta_{tk}c_k=\sum_k\left(\sum_t x_ta_{kt}\right)c_k.
$$
This will be trivially true, if the coefficients of all $c_k$:s vanish, that is, is the equation
$$
\sum_{t=0}^{mn}a_{kt}x_t=0 \qquad(**)
$$
holds for all $k=0,1,2,\ldots,mn-1$. Here there are $mn$ linear homogeneous equations on the $mn+1$ unknowns $x_t$. Therefore linear algebra says that we are guaranteed to succeed in the sense that there exists a non-trivial vector
$(x_0,x_1,\ldots,x_{mn})$ of rational numbers that is a solution of $(**)$. Furthermore, by multiplying with the least common multiple of the denominators,
we can make all the $x_t$:s integers.
The polynomial
$$
F(x)=\sum_{t=0}^{mn}x_tx^t
$$
is then an answer.
Let's do your example of $f(x)=x^2-1$ and $g(x)=x^2+3x+2$. Here $f(\alpha)=0$
tells us that $\alpha^2=1$. Similarly $g(\beta)=0$ tells us that $\beta^2=-3\beta-2$. This is all we need from the polynomials. Here $c_0=1$, $c_1=\beta$,
$c_2=\alpha$ and $c_3=\alpha\beta$. Let us write the power $(\alpha\beta)^t$,
$t=0,1,2,3,4$ in terms of the $c_k$:s.
$$
(\alpha\beta)^0=1=c_0.
$$
$$
(\alpha\beta)^1=\alpha\beta=c_3.
$$
$$
(\alpha\beta)^2=\alpha^2\beta^2=1\cdot(-3\beta-2)=-2c_0-3c_1.
$$
$$
(\alpha\beta)^3=\alpha\beta(-3\beta-2)=\alpha(-3\beta^2-2\beta)=\alpha(9\beta+6-2\beta)=\alpha(7\beta+6)=6c_2+7c_3.
$$
$$
(\alpha\beta)^4=(-3\beta-2)^2=9\beta^2+12\beta+4=(-27\beta-18)+12\beta+4=-14-15\beta=-14c_0-15c_1.
$$
We are thus looking for solutions of the homogeneous linear system
$$
\left(\begin{array}{ccccc}
1&0&-2&0&-14\\
0&0&-3&0&-15\\
0&0&0&6&0\\
0&1&0&7&0
\end{array}\right)
\left(\begin{array}{c}x_0\\x_1\\x_2\\x_3\\x_4\end{array}\right)=0.
$$
Let us look for a solution with $x_4=1$ (if the polynomials you started with
are monic, then this always works AFAICT). The third equation tells us that we should have $x_3=0$. The second equation allows us to solve that $x_2=-5$. The last equation and our knowledge of $x_3$ tells that $x_1=0$. The first equation
then tells that $x_0=4.$ This gives us the output
$$
x^4-5x^2+4.
$$
The possibilities for $\alpha$ are $\pm1$ and the possibilities for $\beta$ are $-1$ and $-2$. We can easily check that all the possible four products $\pm1$ and $\pm2$ are zeros of this quartic polynomial.
My solution to the linear system was ad hoc, but there are known algorithms for that: elimination, an explicit solution in terms of minors,...
I think I got the proof that no such real polynomial with degree $ \geq 6$ exists.
Let $n \geq 6$
Suppose for contradiction that $z_1,\ldots,z_n \in \mathbb R-\{0\}^n$ are such that $(X-z_1)...(X-z_n)=X^n+\sum_{k=1}^{n-1}z_iX^{n-i}$
Then three useful identities appear $$\sum_{k=1}^{n}z_k=-z_1 \; \; \; \;(1)$$
$$\sum_{\large1\leq i<j \leq n}z_iz_j=z_2 \; \; \; \;(2)$$
$$\prod_{k=1}^n z_k=(-1)^n z_n \; \; \; \;(3)$$
Since $$(\sum_{k=1}^{n}z_k)^2=\sum_{k=1}^{n}z_k^2+2\sum_{\large1\leq i<j \leq n}z_iz_j$$it follows that$$z_1^2=2z_2+\sum_{k=1}^{n}z_k^2$$
Hence $$0< \sum_{k=2}^{n}z_k^2=-2z_2 \; \; \; \;(4)$$ and $$0<\sum_{k=3}^{n}z_k^2=1-(z_2+1)^2 \; \; \; \;(5) $$
$(4)$ and $(5)$ imply $$\; \; \; \;-2<z_2<0 \; \; \; \;(6)$$
thus $(6)$ and $(4)$ imply $$0<\sum_{k=2}^{n}z_k^2 < 4 \; \; \; \; (7)$$
Also $(6)$ and $(5)$ imply $$0<\sum_{k=3}^{n}z_k^2 \leq 1 \; \; \; \; (8)$$
By AM-GM, $$\left(|z_3|^2\ldots|z_{n-1}|^2 \right)^{1/(n-3)} \leq \frac{1}{n-3}\sum_{k=3}^{n-1}z_k^2 \leq \frac{1}{n-3}\sum_{k=3}^{n}z_k^2$$
Hence
$$|z_3|^2\ldots|z_{n-1}|^2 \leq \left(\frac{1}{n-3}\sum_{k=3}^{n}z_k^2\right)^{n-3} $$
Squaring, $$|z_3|\ldots|z_{n-1}| \leq \left(\frac{1}{n-3}\sum_{k=3}^{n}z_k^2\right)^{\large \frac{n-3}{2}} \leq_{ \large (8)} \dfrac{1}{{(n-3)}^{(n-3)/2}} \; \; \; \; (9)$$
By triangle inequality $(1)$, and Cauchy-Schwarz
$$2|z_1| \leq \sum_{k=2}^{n}|z_k| \leq \sqrt{n-1} \sqrt{\sum_{k=2}^{n}z_k^2} $$
Hence by $(7)$,
$$|z_1| \leq \sqrt{n-1} \; \; \; \; (10)$$
Rewriting $(6)$ as $$|z_2|\lt2 \; \; \; \; (11) $$
Recalling $(3)$ (with $z_n$ cancelled from both sides) and putting together $(9)$, $(10)$ and $(11)$, we have
$$1=|z_1||z_2||z_3|\cdots|z_{n-1}| < \dfrac{ 2\sqrt{n-1}}{{(n-3)}^{(n-3)/2}}$$
This inequality fails for $n\geq 6$.
Contradiction.
I can't prove anything for $n=5$ so maybe the conjecture doesn't hold.
Best Answer
Let your polynomial be $P(x) = \sum_{k=0}^n c_i x^i$. Let $A_k$ be the sets of nonnegative integers $i$ such that $c_i = k$, $k=0,1,2,3$. Thus $$ \eqalign{n &= \sum_{i \in A_1} 2^i + 2 \sum_{i \in A_2} 2^i + 3 \sum_{i \in A_3} 2^i\cr &= \sum_{i \in A_1 \cup A_3} 2^i + 2\sum_{i \in A_2 \cup A_3} 2^i}$$ Given any nonnegative integers $a,b$ such that $n = a + 2 b$, we can find $A_0, A_1, A_2, A_3$ such that $a = \sum_{i \in A_1 \cup A_3} 2^i$ and $b = \sum_{i \in A_2 \cup A_3} 2^i$, namely $A_0$ is the set of $i$ such that the base-2 digit in the "$2^i$" place for both $a$ and $b$ are $0$, $A_1$ where the digit is $1$ for $a$ and $0$ for $b$, $A_2$ where the digit is $0$ for $a$ and $1$ for $b$, $A_3$ where the digit is $1$ for both.
Now count how many ways there are to write $n=a+2b$...