We begin by assuming that a non-constant complex polynomial $$p(z)=a_n z^n+a_{n-1}z^{n-1}+...+a_1 z+a_0,$$ where $a_0 \neq 0$, doesn't vanish in $\mathbb{C}$. Therefore $1/p$ is also an analytical function everywhere. Note that $(p(z)-a_0)/z$ is a polynomial and therefore, due to Cauchy's theorem, the following integral must be zero.
$$\int_{S_r^1}\frac{(p(z)-a_0)/z}{p(z)}dz=\int_{S_r^1}\frac{a_nz^{n-1}+a_{n-1}z^{n-2}+...+a_1}{a_nz^n+a_{n-1}z^{n-1}+...+a_1 z+a_0}dz=0.$$
On the other hand
$$\int_{S_r^1}\frac{a_nz^{n-1}+a_{n-1}z^{n-2}+...+a_1}{a_nz^n+a_{n-1}z^{n-1}+...+a_1 z+a_0}dz$$
$$=\int_{0}^{2\pi}\frac{a_n(re^{i\theta})^{n-1}+a_{n-1}(re^{i\theta})^{n-2}+...+a_1}{a_n(re^{\theta})^n+a_{n-1}(re^{i\theta})^{n-1}+...+a_1 (re^{i\theta})+a_0}(ire^{i\theta})d\theta$$
$$=\int_{0}^{2\pi}i d\theta - \int_{0}^{2\pi}\frac{a_0 i}{a_n(re^{i\theta})^n+a_{n-1}(re^{i\theta})^{n-1}+...+a_1 (re^{i\theta})+a_0}d\theta$$ $$=2\pi i -\int_{0}^{2\pi}\frac{a_0i}{p(re^{i\theta})}d\theta.$$
Let $r \rightarrow \infty$ and the integral approaches value $2\pi i$ - a contradiction. Therefore $1/p$ can't be entire and $p$ must vanish somewhere in the complex plane.
EDIT: I have changed this post and deleted the idea that the integral $\int_{\partial D_r}\frac{(p(z)-a_0)/z}{p(z)}dz=0$ could be evaluated with the fundamental theorem of calculus. Now, as it stands, this proof is essentially the same as the one that Mr. José Carlos Santos points out in his comment.
Have a look at pages 120-125 of my course notes.
If by the Fundamental Theorem of Calculus you mean the residue Theorem / Cauchy's integral formula (which can be seen as consequences of Stokes' Theorem, i.e. a generalized version of the Fundamental Theorem of Calculus) the answer is yes.
Assume that $p(z)=z^n+a_{n-1}z^{n-1}+\ldots+a_0\in\mathbb{C}[z]$ fulfills $n\geq 1$, $a_0\neq 0$ and has no complex roots. In such a case $f(z)\stackrel{\text{def}}{=}\frac{1}{z\cdot p(z)}$ is a meromorphic function with a unique singularity, which is the simple pole at the origin. By the residue Theorem, for any $R>0$ we have
$$ \oint_{|z|=R}\frac{dz}{z\cdot p(z)} = \frac{2\pi i}{p(0)} \neq 0 \tag{1}$$ but since $|p(z)|\to +\infty$ as $|z|\to +\infty$, the LHS of $(1)$ is arbitrarily close to zero by the triangle inequality. This contradiction proves that any non-constant polynomial in $\mathbb{C}[z]$ has at least a complex zero.
Gauss' original proof went close to proving the Fundamental Theorem of Algebra by using real instruments only, but at some point one has to invoke something more-or-less equivalent to $\pi^1(S^1)=\mathbb{Z}$ or to the Jordan curve theorem, since real results only are not powerful enough to prove something about $\mathbb{C}\simeq \mathbb{R}^2$. Have a look at this MO thread, too.
It is worth mentioning an equivalent version of the Fundamental Theorem of Algebra: by associating a polynomial with its companion matrix, we get that in order to prove the FTA it is enough to show that
For such a purpose, one may invoke the power iteration.