Proof the Fibonacci numbers are not a polynomial.

Taking successive differences of a nonzero polynomial should result in a polynomial of the next smallest degree. That is, if $p$ is degree $n$, then $p(x)-p(x-1)$ should be of degree $n-1$.

But if $p(i)$ gives Fibonacci numbers, then $p(i)-p(i-1)=p(i-2)$. So $\deg p=\deg(p)-1$, a contradiction. (This is a different take on your argument (which is great) since you asked about alternatives.)

(A riff on a deleted answer:)

Any polynomial sequence has a rational generating function of the form $\frac{P(x)}{(1-x)^k}$. This can be seen by repeatedly differentiating the geometric series.

The Fibonacci sequence has generating function $\frac{x}{1-x-x^2}$, which is not of this form. Since generating functions are unique, it follows that the Fibonacci sequence is non-polynomial.

If we consider ratios of the Fibonacci numbers we can come up with a quick growth rate: $$\frac{F_{n+1}}{F_{n}} = \frac{F_{n} + F_{n-1}}{F_n} = 1 + \frac{F_{n-1}}{F_n}<2$$ and $$\frac{F_{n-1}}{F_{n}} = \frac{F_{n-1}}{F_{n-1}+F_{n-2}} > \frac{F_{n-1}}{2 F_{n-1}} = 1/2$$ which means $$1.5 < \frac{F_{n+1}}{F_n} < 2.$$ Hence, $(1.5)^n < F_n < 2^n$ for $n>1$ which means that the growth rate for the Fibonacci numbers is exponential.

Suppose $p(i)=F_i$ for some polynomial (of degree $m$) then the polynomial can be written as $$p(x) = a_m x^m + a_{m-1} x^{m-1} + \cdots + a_0.$$ Thus $$|F_n| = |p(n)| \le n^m \sum_{i=1}^m |a_m| := Cn^m.$$ This means $$(1.5)^n < Cn^m$$ for all $n$.

We can demonstrate that this inequality cannot hold for all $n$. It is clearer when logarithms are used: $$(1.5)^n < Cn^m$$ which means $$n \ln(1.5) < \ln(C) + m \ln(n)$$ and $$\ln(1.5) < \frac{\ln(C)}{n} + m \frac{\ln(n)}{n}.$$ The term $\ln(C)/n$ goes to zero as $n \to \infty$ and so does $\ln(n)/n$. However, since $\ln(1.5) > 0$ this is a contradiction.