Step 1: Suppose $P$ has degree $d$. Let $Q$ be the polynomial of degree at most $d$ with $Q(x)=q_x$ for $0\leq x\leq d$. Since the $q_x$ are all integers, $Q$ has rational coefficients, and there exists $k$ so that $kQ$ has integer coefficients. Then $m-n|kQ(m)-kQ(n)$ for all $m,n\in \mathbb N_0$.
Step 2: We show that $Q$ is the desired polynomial.
Let $x>n$ be given. Now
$$kq_x\equiv kq_m\pmod{x-m}\text{ for all integers }m\in[0,d]$$
Since $kQ(x)$ satisfies these relations as well, and $kq_m=kQ(m)$,
$$kq_x\equiv kQ(x)\pmod{x-m}\text{ for all integers }m\in[0,d]$$
and hence
$$kq_x\equiv kQ(x)\pmod{\text{lcm}(x,x-1,\ldots, x-d)}. \;(1)$$
Now
\begin{align*} \text{lcm}(x,x-1,\ldots, x-i-1)&=\text{lcm}[\text{lcm}(x,x-1,\ldots, x-i),x-i-1]\\ &=\frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[\text{lcm}(x,x-1,\ldots, x-i),(x-i-1)]}\\ &\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[x(x-1)\cdots(x-i),(x-i-1)]}\\ &\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{(i+1)!} \end{align*}
so by induction $\text{lcm}(x,x-1,\ldots, x-d)\geq \frac{x(x-1)\cdots (x-d)}{d!(d-1)!\cdots 1!}$. Since $P(x), Q(x)$ have degree $d$, for large enough $x$ (say $x>L$) we have $\left|Q(x)\pm\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}\right|>P(x)$. By (1) $kq_x$ must differ by a multiple of $\text{lcm}(x,x-1,\ldots, x-d)$ from $kQ(x)$; hence $q_x$ must differ by a multiple of $\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}$ from $Q(x)$, and for $x>L$ we must have $q_x=Q(x)$.
Now for any $y$ we have $kQ(y)\equiv kQ(x)\equiv kq_x \equiv kq_y\pmod{x-y}$ for any $x>L$. Since $x-y$ can be arbitrarily large, we must have $Q(y)=q_y$, as needed.