Every Function in a Finite Field is a Polynomial Function

It might be interesting to you to look up the Lagrange Interpolation Formula. Given a function $f$ from the finite field to itself, it will give you an explicit polynomial $P$ such that the associated polynomial function is equal to $f$.

Yes, your second method works and indeed generalizes nicely to functions in $n$ variables.

A similar method to show that every function $f: \mathbb{F}_q^n \rightarrow \mathbb{F}_q$ is given by a polynomial in which the degree in each variable is at most $q-1$ is to give an explicit polynomial formula for the "Dirac delta function" $\mathbb{1}_0(x)$ which is equal to $1$ if $x = (0,\ldots,0)$ and $0$ otherwise. Indeed, we have

$\mathbb{1}_0(x_1,\ldots,x_n) = \prod_{i=1}^n (1-x_i^{q-1})$

as it is a pleasant and easy exercise to check.

Again a cardinality argument shows that any such function $f$ has a unique representation by a reduced polynomial, i.e., by a polynomial whose degree in each variable is at most $q-1$. These observations lead quickly to a proof of the celebrated Chevalley-Warning Theorem: see these notes for a treatment of all these topics.

First off, a finite field doesn't necessarily have $p$ elements for $p$ prime. For every prime $p$ and natural number $m>0$ there is a finite field with $p^m$ elements.

Second, your approach is sound - the only piece you're missing is that your matrix is a Vandermonde matrix which, over any field, has a simple expression for its determinant.

There is a very simple argument based only on dimension and root counting. You want to show that the map$~g$ from the polynomials in $\def\Fq{{\Bbb F_q}}\Fq[X]$ to their polynomial functions in $\Fq^\Fq=\{\,f:\Fq\to\Fq\mid\,\}$ is surjective. It is easy to see the map is $\Fq$-linear and that $\dim(\Fq^\Fq)=q$. It is actually easier to show the stronger statement that the restriction$~\tilde g$ of$~g$ to the subspace $V=\{\,P\in\Fq[X]\mid\deg(P)<q\,\}$ is bijective (so in particular$~\tilde g$ is surjective, and a fortiori so is $g$).

Now $\dim(V)=q$ so$~\tilde g$ is a linear map between two vector spaces of the same dimension; such maps are bijective if and only if they are injective, i.e., have $\{0\}$ as kernel. Now $\ker(\tilde g)$ consists of those $P\in V$ whose polynomial function is the zero function. The part $P\in V$ means that $\deg(P)<q$, and the polynomial function being zero means that all $q$ elements of$~\Fq$ are roots of$~P$. It is well known that a nonzero polynomial over a field cannot have more roots than its degree. This shows that $\ker(\tilde g)=\{0\}$, so $\tilde g$ is bijective, as desired.