I hope the following will mostly satisfy Bjorn. It is a proof by induction which naturally skips over the base case and is at the undergraduate level. I saw the argument for the first time today in the paper containing 10 proofs in Russian of the Fundamental Theorem of Algebra which Ilya Nikokoshev made a link to in his answer to a question asking for lots of different proofs of that theorem. Here we go:
Claim: A polynomial (over a field) of nonzero degree has no more roots than its degree.
Proof: We prove this by induction on the degree $n$ of the polynomial. Assume that the polynomial $p(X) = a_nX^n + \cdots + a_1X + x_0$ of degree $n$ has at least $n+1$ different roots $r_1,\dots, r_{n+1}$. Consider the polynomial $q(X) = a_n(X-r_1)\cdots (X-r_n)$. We have $p(X) \not= q(X)$ since $p(r_{n+1}) = 0$ and $q(r_{n+1}) \not= 0$. The difference $d(X) = p(X) - q(X)$ is a nonzero polynomial of degree less than $n$ having at least $n$ roots $r_1,\dots,r_n$. This contradicts the inductive hypothesis. QED
One aspect of this which does not fit Bjorn's request is that this argument uses ordinary induction, not strong induction. But really, is that such a big deal? I suspect his main interest is seeing an inductive argument at all where the base case is naturally not mentioned, rather than specifically one using strong induction.