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.