(Non-vanishing is established by multiplying by $n!^2$ and getting an expression which is 1 modulo $n$.)

Robert Israel's answer and the comments following it settle your problem completely, but here's a general strategy that often works:

Suppose you have a sum of the form $S(n) = \sum_{k=0}^{n} f(n,k)$, where $f$ is "hyper-geometric" in the sense that $f(n+1,k)/f(n,k), f(n,k+1)/f(n,k)$ are rational functions.

- Find the maximum of $|f(n,k)|$ as a function of $k$ ($n$ fixed). This is rather easy because $|f(n,k+1)|/|f(n,k)|$ is the absolute value of a rational function. In your specific problem, it is $\frac{n-k}{(k+1)^2}$, so $|f(n,k)|$ increases for $k \lesssim \sqrt{n}$ and then it decreases. The sign of the largest term is usually the resulting sign of the sum.
- Suppose the maximum is attained at $k=M(n)$. Focus on estimating the sum around $k=M(n)$ (the rest of the terms should be easier to bound, as we know they are smaller, the decay is exponential usually). Specifically, Stirling's approximation is usually enough for estimating $\sum_{k=-\Delta}^{\Delta} f(n,M(n)+k)$ - plugging Stirling and using some Taylor series estimates ($\Delta$ is chosen so that the Taylor series estimates are valid), we get a sum that can sometimes be evaluated even by comparing to a Riemann's integral.

This is a rather elementary approach; Asymptotic methods such as steepest descent can yield *much* better results if you can express your sum as the coefficient of some analytic function. This can be done in your case as we have the relevant generating function: $e^{\frac{t}{1+t}-\ln(1+t)}$. See de Bruijn' "Asymptotic Methods in Analysis" (the example in section 4.7 is solved twice in the text - Laplace' method and Steepest descent, and it is reminiscent of your sum as it contains a sign-changing term).

The sign-changing property of your sum makes other nice methods obsolete. Hayman's method, for example, works in extracting the coefficients of $e^{P(t)}$ where $P$ is a function satisfying some positivity conditions ($\frac{t}{1+t}-\ln(1+t)$ is not admissible as its coefficients are sign-changing, but the method should succeed in approximating your sum if we remove the sign-changing term).