There's a nice proof of this which uses Liouville's theorem. For convenience I'll restate it here:

Theorem (Liouville) Let f be holomorphic and bounded on the entire complex plane. Then f is constant.

Theorem (Fundamental theorem of algebra) Let p be a non-constant polynomial with complex coefficients. Then p has a root, ie. there is a complex number z with p(z) = 0.

Proof Suppose there is no such number z. We show that p is constant.

Let f = 1/p. Then f is holomorphic wherever p is non-zero, which by assumption is the whole complex plane.

Moreover, p is a polynomial, so |p(w)| tends to infinity as |w| tends to infinity; consequently, |f(w)| tends to 0 as |w| tends to infinity. So there exists M such that |f(w)| < 1 whenever |w| > M. And f is holomorphic, and hence bounded, on the compact set {w : |w| <= M}. So f is bounded on the complex plane.

So f satisfies the conditions for Liouville's theorem, and must be constant. Hence p is constant. QED