The required polynomials are $P = 0$, $P = 1$, $P = (X - 1)^2$, $P = X(X - 1)\cdots(X - k)$ and $P = X(X - 1)\cdots(X - k)(X - k - 2)^2$ for some non-negative integer $k$. The verification is routine and is hence omitted.

We first deal with the case $P(0) = 1$. The polynomials $P_1 = 1$ and $P_2 = (X-1)^2$ both satisfy the condition in the statement and $P_1(0) = P_2(0) = 1$.

We will prove that either $P = P_1$ or $P = P_2$. Consider an index $i$ such that $P(1) = P_i(1)$ and let $\tilde{P} = P - P_i$.
Induct on $n$ to show that $\tilde{P}(n) = 0$ for all non-negative integers $n$. The base cases $n = 0$ and $n = 1$ are clear. For the inductive step, assume $\tilde{P}(m) = 0$ for all non-negative integers $m < n$. Then $X(X-1)\cdots(X-(n-1))$ divides $\tilde{P}$, so $n!$ divides $\tilde{P}(n)$. As $0 < P_i(n) < n!$, it follows that $|\tilde{P}(n)| = |P(n) - P_i(n)| < n!$, so $\tilde{P}(n) = 0$.
Consequently, $\tilde{P}$ has infinitely many roots, so it vanishes identically; that is, $P = P_i$, as desired.

Finally, we deal with the case $P(0) = 0$. Assume $P$ is non-zero. Let $P(X) = XQ(X - 1)$, where $Q$ has integer coefficients. Then $0 \le Q(n) \le n!$ for all non-negative integers $n$. If $Q(0) = 0$, repeat the argument for $Q$ and so on and so forth, all the way down to some polynomial with a non-zero constant term — this is clearly the case, as $P$ is non-zero and degrees strictly decrease in the process. By the preceding, such a polynomial is either $1$ or $(X - 1)^2$. An obvious induction then shows that $P$ has one of the last two forms mentioned in the beginning.