Solution:
We claim that the only such polynomials are of the form $P(x)=\frac{1}{i}(x+j)$ for some integers $i \neq 0, j$.
Let $\mathcal{R}$ be the set $\{P(n) \mid n \in \mathbb{Z}\}$.

Without loss of generality, we may assume that the leading coefficient of $P(x)$ is positive; otherwise we can consider $-P(x)$. If the polynomial $P(x)$ has even degree, then it must have a minimum value $m$. Then all integers less than $m$ are in the set $\mathbb{Z} \backslash \mathcal{R}$, so it cannot be finite. Thus $P(x)$ must have odd degree.

Since the set $\mathbb{Z} \backslash \mathcal{R}$ is finite, there exists some $M_{1}$ such that $x \in \mathcal{R}$ for all integers $x>M_{1}$. As $P(x)$ has odd degree and positive leading coefficient, there exists some $M_{2}$ such that $P\left(M_{2}\right)>M_{1}$, $P(x) \leq P\left(M_{2}\right)$ for all $x \leq M_{2}$ and $P(x)$ is increasing on $\left[M_{2}, \infty\right)$. Let $M=\max \left\{M_{1}, M_{2}\right\}$.

Choose an integer $n$ such that $n>M$ and $P(n+1)>P(n)+1$. Letting $s=\lfloor P(n)+1\rfloor$, we claim there is no such integer $x$ such that $P(x)=s$. Consider the following cases:
- $x \leq M_{2}$. Then $P(x) \leq P\left(M_{2}\right) \leq P(n)<s$.
- $M_{2}<x \leq n$. Then $P(x) \leq P(n)<s$ as $P(x)$ is increasing.
- $x>n$. Then $x \geq n+1$ and $P(x) \geq P(n+1)>P(n)+1 \geq s$, as $P(x)$ is increasing.

Thus $s$ is in the set $\mathbb{Z} \backslash \mathcal{R}$. However, $s>P(n)>P\left(M_{2}\right)>M_{1}$, contradicting the definition of $M_{1}$. Thus, $P(n+1) \leq P(n)+1$ for all integers $n>M$.

Let $d$ be the degree of $P(x)$. Observe $P(n+1)-P(n)$ is a polynomial of degree $d-1$ with the same positive leading coefficient as $P(x)$. If $d-1 \geq 1$, then $P(n+1)-P(n)$ will become arbitrarily large as $n$ increases, contradicting $P(n+1) \leq P(n)+1$ for all integers $n>M$.

Therefore, $d=1$, and $P(x)=a x+b$ for some real numbers $a \neq 0$ and $b$. As $\mathbb{Z} \backslash \mathcal{R}$ is finite, only finitely many pairs of integers $(t, t+1)$ are not in $\mathcal{R}$. Thus, there exists distinct integers $n_{1}$ and $n_{2}$ such that $P\left(n_{1}\right)=t$ and $P\left(n_{2}\right)=t+1$. It follows that
$$1=P\left(n_{2}\right)-P\left(n_{1}\right)=a\left(n_{2}-n_{1}\right) \Longrightarrow a=\frac{1}{n_{2}-n_{1}}=\frac{1}{i}$$
for some integer $i \neq 0$. Furthermore,
$$P\left(n_{1}\right)=t=a n_{1}+b \Longrightarrow b=\frac{i t-n_{1}}{i}=\frac{j}{i}$$
for some integer $j$. Hence $P(x)$ must be of the form $\frac{1}{i}(x+j)$ for integers $i \neq 0, j$. All such polynomials clearly satisfy the given conditions.