Suppose you give me a complex number: can I find a polynomial whose roots include it?
As you noted, the answer is trivial for complex coefficients: if you want a polynomial with the root $w$, then $P(z) = z-w$ will do. What about a polynomial with real coefficients? There too, it's relatively straightforward; the polynomial $P(x) = (x-w)(x-\bar{w}) = x^2-2\mathcal{R}(w)x+\left|w\right|^2$ has real coefficients and has roots $w$ and $\bar{w}$.
What if I have rational coefficients?
The answer here is no, for the exact same reason as for integer coefficients; the two cases are equivalent. To see why, consider as an example the polynomial $P(x) = \frac{1}{5}x^3-\frac{7}{3}x^2+\frac{5}{4}x-\frac{17}{8}$. Then $P(x)$ has the same roots as the polynomial $Q(x) = 120P(x) = 24x^3-280x^2+150x-255$ obtained by multiplying $P$ by the LCM of the denominators of all its coefficients.
Gaussian integers?
Again no, by two separate results: one relatively straightforward, but one more subtle but much more far-reaching. The straightforward way of seeing this is again by using the complex conjugate: if $P(x)$ is a polynomial with Gaussian integers for coefficients, then $Q(x) = P(x)\bar{P}(x)$ has all of $P$'s roots among its roots, but has (real) integer coefficients; for instance, if $P(x) = x^2+(2+i)x+3i$, then $\bar{P}(x) = x^2+(2-i)x-3i$ and $P(x)\bar{P}(x) = x^4+(2+i)x^3+(2-i)x^3+3ix^2-3ix^2+(2+i)(2-i)x^2 + 3i(2+i)x -3i(2-i)x +(3i)^2 = x^4+4x^3+5x^2-6x-9$.
The more abstract reason, though, is that the algebraic numbers (defined as 'roots of polynomials with integer coefficients') are algebraically closed: any number that's the root of a polynomial with algebraic numbers for coefficients (which includes all the cases you mentioned above, as well as many more) is algebraic itself (and thus already the root of a polynomial with integer coefficients). This can be shown by, essentially, clearing coefficients: for an example of how this works, suppose we want to find an integer polynomial whose roots include the roots of the polynomial $P(x) = x^2-\sqrt{2}x+1$. Well, first rewrite the equation $P(x) = 0$ by moving the $\sqrt{2}$ term to the left, giving $\sqrt{2} x = x^2+1$; now by squaring both sides (which may introduce new roots, but won't cost the roots we have) we get $2x^2 = \left(x^2+1\right)^2 = x^4+2x^2+1$, or $x^4+1=0$; thus, any root of $P(x) = x^2-\sqrt{2}x+1$ is also a root of $Q(x) = x^4+1$. A (much!) more complicated but similar procedure will allow all algebraic coefficients to be 'cleared' from a polynomial, giving a polynomial with only integer coefficients and roots a superset of the original polynomial's roots. Taking the contrapositive of this indicates that no transcendental number can be the root of any polynomial with algebraic coefficients, whether real or complex.
In fact, it's possible to go one step farther still: we can say with confidence that, for instance, not every number is the root of a polynomial with coefficients any algebraic expression of whole numbers, $e$ and $\pi$! This time the argument is more abstract still: there are only countably many '$\pi e$-algebraic' expressions, so there are only countably many polynomials with $\pi e$-algebraic expressions for coefficients; and since each polynomial has finitely many roots, there are only countably many such roots. But because there are uncountably many real numbers, our set of roots must exclude some (in fact, almost all) real numbers. This argument shows that the reals have infinite (in fact, uncountably infinite) transcendence degree over the rationals; no finite (or countable) number of additional reals that are made available as coefficients will let you 'capture' all the real numbers (or complex numbers, of course) as roots of polynomials.
Method of FTA:
$$P(\overline z)=\sum_{k=0}^{2n+1}a_k\overline z^k=\sum_{k=0}^{2n+1}\overline a_k\overline{z^k}=\sum_{k=0}^{2n+1}\overline{a_kz^k}=\overline{\sum_{k=0}^{2n+1}a_kz^k}=\overline{P(z)}$$
which states $z$ is a root for $P(z)=0$ iff its complex conjugate $\bar z$ is. According to FTA, there are odd number of roots for a polynomial of odd degree. That implies there must be one single root $z$ satisfying $z=\bar z$, hence the real root.
Method of IVT:
$$\frac{P(x)}{x^{2n+1}}=1+\sum_{k=0}^{2n}a_k\frac{x^k}{x^{2n+1}}=1+\sum_{k=0}^{2n}a_kx^{k-(2n+1)}$$
For any $\varepsilon>0$, there exists $N>0$ such that for all $|x|>N$, $\left|\sum_{k=0}^{2n}a_kx^{k-(2n+1)}\right|<\varepsilon$. Hence for $x>N$, we have $P(x)>x^{2n+1}-\varepsilon x^{2n+1}>0$ and similarly for $x<-N$, we have $P(x)<0$. Then IVT implies there exists some $y$ such that $P(y)=0$.
Best Answer
The theorem may as well state that every polynomial equation of degree $n$ has exactly $n$ roots (counted with their multiplicity). The statements are equivalent, for, if your polynomial $p(z)$ of degree $n$ has one root $\lambda$, then you can factor it as
$$ p(z) = (z-\lambda)q(z), $$ where the degree of $q$ is $n-1$ Then you can recursively apply the result to $q$, until you reach a polynomial of degree 1.