I hope the following will 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
[EDIT: IGNORE what follows in the next paragraph, which was in the original post, since I confused myself about strong vs. ordinary induction. The above proof is by strong induction since the degree of d(X) is merely less than n and not necessarily n-1 itself.]
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.