Add the last row multiplied by -1 to all other rows, and we get,
det$|V|$=det$\left|\begin{array}{}
0 & x_1-x_n & x_1^2-x_n^2 & \cdots & x_1^n-x_n^n \\
0 & x_2-x_n & x_2^2-x_n^2 & \cdots & x_2^n-x_n^n \\
\vdots & \vdots & \vdots & & \vdots \\
0 & x_{n-1}-x_n & x_{n-1}^2-x_n^2 & \cdots & x_{n-1}^n-x_n^n \\
1 & x_n & x_n^2 & \cdots & x_n^n \\
\end{array} \right|
$
=det$\left|\begin{array}{}
x_1-x_n & x_1^2-x_n^2 & \cdots & x_1^n-x_n^n \\
x_2-x_n & x_2^2-x_n^2 & \cdots & x_2^n-x_n^n \\
\vdots & \vdots & & \vdots \\
x_{n-1}-x_n & x_{n-1}^2-x_n^2 & \cdots & x_{n-1}^n-x_n^n \\
\end{array} \right|
$
=$\prod\limits_{k=1}^{n-1}(x_k-x_n)$ det$\left|\begin{array}{}
1 & x_1+x_n & x_1^2+x_1x_n+x_n^2 & \cdots & \sum \limits_{k=0}^{n-1}x_1^{n-k-1}x_n^{k} \\
1 & x_2+x_n & x_2^2+x_2x_n+x_n^2 & \cdots & \sum \limits_{k=0}^{n-1}x_2^{n-k-1}x_n^{k} \\
\vdots & \vdots & \vdots & & \vdots \\
1 & x_{n-1}+x_n & x_{n-1}^2+x_{n-1}x_n+x_n^2 & \cdots & \sum \limits_{k=0}^{n-1}x_{n-1}^{n-k-1}x_n^{k} \\
\end{array} \right|
$
=$\prod\limits_{k=1}^{n-1}(x_k-x_n)$ det$|V_1|$
In $V_1$, first add 1st column multiplied by $-x_n$ to 2nd column, and add 1st column multiplied by $-x_n^2$ to 3nd column, ..., and add 1st column multiplied by $-x_n^{n-1}$ to $(n-1)$'s column, we get
det$|V_1|$ = det$\left|\begin{array}{}
1 & x_1 & x_1^2+x_1x_n & \cdots & \sum \limits_{k=0}^{n-2}x_1^{n-k-1}x_n^{k} \\
1 & x_2 & x_2^2+x_2x_n & \cdots & \sum \limits_{k=0}^{n-2}x_2^{n-k-1}x_n^{k} \\
\vdots & \vdots & \vdots & & \vdots \\
1 & x_{n-1} & x_{n-1}^2+x_{n-1}x_n & \cdots & \sum \limits_{k=0}^{n-2}x_{n-1}^{n-k-1}x_n^{k} \\
\end{array} \right|
$
Then add 2nd column multiplied by $-x_n$ to 3rd column, ..., and add 2nd column multiplied by $-x_n^{n-2}$ to $(n-1)$'s column, we get
det$|V_1|$ = det$\left|\begin{array}{}
1 & x_1 & x_1^2 & \cdots & \sum \limits_{k=0}^{n-3}x_1^{n-k-1}x_n^{k} \\
1 & x_2 & x_2^2 & \cdots & \sum \limits_{k=0}^{n-3}x_2^{n-k-1}x_n^{k} \\
\vdots & \vdots & \vdots & & \vdots \\
1 & x_{n-1} & x_{n-1}^2 & \cdots & \sum \limits_{k=0}^{n-3}x_{n-1}^{n-k-1}x_n^{k} \\
\end{array} \right|
$
Repeat above process, and use induction hypothesis, we have
det$|V_1|$ = det$\left|\begin{array}{}
1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\
1 & x_2 & x_2^2 & \cdots & x_2^{n-1} \\
\vdots & \vdots & \vdots & & \vdots \\
1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-1} \\
\end{array} \right|
$ = $\prod_{1\le i<j\le n-1} (x_j-x_i)$
So finally
det$|V|$ =$\prod\limits_{k=1}^{n-1}(x_k-x_n)$ det$|V_1|$ = $\prod_{1\le i<j\le n} (x_j-x_i)$
If you have studied eigenvalues and eigenvectors there is a very easy proof.
Let $A$ be your $n\times n$ matrix, with $n\ge2$. Then $A+I$ is the matrix consisting entirely of $1$s, which clearly has $n-1$ zero rows after row-reduction. Therefore $A$ has eigenvalue $-1$, repeated (at least) $n-1$ times, and since ${\rm trace}(A)=0$, the other eigenvalue is $n-1$.
Since every eigenvalue of $A$ is non-zero, the determinant of $A$ is non-zero, so $A$ is invertible.
Best Answer
This is really not about characteristic polynomials at all, just a fundamental property of determinants (over any commutative ring $R$, where here we take $R$ to be the ring of polynomials in $t$ over your field), namely $$ \det\pmatrix{B&0\\C&D}=\det(B)\det(D). $$ You can apply this immediately for the characteristic polynomial, since the act of transforming $A$ into $xI_n-A$ amounts to transforming $B$ into $tI_k-A$, and $D$ into $xI_{n-k}-D$ (also $C$ becomes $-C$).
That property of determinants is the subject of this other question, and in my opinion the best proof is really directly from the (Leibniz formula) definition of determinants, as I detailed in my answer to that question. In particular, I would want to avoid using a property like $\det(XY)=\det(X)\det(Y)$, which although of course true, is actually quite a bit harder to prove directly from the definition.