This is one of the proofs currently on the nLab. My goal in writing it was to see how elementary I could make it, that if you squint a little it might have been a proof from the late $18^{th}$ century. I think it's pretty close; it uses the Bolzano-Weierstrass theorem, proven by Bolzano in 1817. (It's also similar in form to the answer by Timothy Gowers http://mathoverflow.net/a/16671/2926, but with more detail, suitable perhaps for a presentation to an advanced calculus class.)
Let $f\colon \mathbb{C} \to \mathbb{C}$ be a nonconstant polynomial mapping, and suppose $f$ has no zero.
Let $s$ be the infimum of values ${|f(z)|}$; choose a sequence $z_1, z_2, z_3, \ldots$ such that ${|f(z_n)|} \to s$. Since $\lim_{z \to \infty} f(z) = \infty$, the sequence $z_n$ must be bounded; by the Bolzano-Weierstrass theorem it has a subsequence $z_{n_k}$ that converges to some point $z_0$. Then ${|f(z_{n_k})|}$ converges to ${|f(z_0)|}$ by continuity, and converges to $s$ as well, so ${|f(z)|}$ attains its absolute minimum $s$ at $z = z_0$. By supposition, $f(z_0) \neq 0$.
The polynomial $f$ may be uniquely written in the form $$f(z) = f(z_0) + g(z)(z - z_0)^n$$ where $g$ is polynomial and $g(z_0) \neq 0$. Put $$F(z) = f(z_0) + g(z_0)(z - z_0)^n$$ and choose $\delta \gt 0$ small so that $${|z - z_0|} = \delta \Rightarrow {|g(z) - g(z_0)|} \lt {|g(z_0)|}.$$
$F$ maps the circle $C = \{z : {|z - z_0|} = \delta\}$ onto a circle of radius $r = {|g(z_0)|}\delta^n$ centered at $f(z_0)$. (This uses the fact that any complex number has an $n^{th}$ root; an $18^{th}$ century mathematician might have invoked Euler's formula or De Moivre's formula.) Choose $z' \in C$ so that $F(z')$ is on the line segment between the origin and $f(z_0)$ (we can always choose $\delta$ so that also $r \lt {|f(z_0)|}$). Then $${|F(z')|} = {|f(z_0)|} - r.$$ We also have $${|f(z') - F(z')|} = {|g(z') - g(z_0)|} {|z' - z_0|^n} \lt {|g(z_0)|} \delta^n = r$$ according to how we chose $\delta$ in 2. We conclude by observing the strict inequality $${|f(z')|} \leq {|F(z')|} + {|f(z') - F(z')|} \lt {|f(z_0)|} - r + r = {|f(z_0)|},$$ which contradicts the fact that ${|f(z)|}$ attains an absolute minimum at $z = z_0$.