The polynomial $ P(x)=4-x(x^2+2x-1)$ has $ P(1)=P(-1)=P(-2)=2$ and $ P(0)=4$. Hence $ n>3$. Next consider a polynomial $ P(x)$ with integer coefficients such that $ P(a)=P(b)=P(c)=P(d)=2$ for four distinct integers $ a,b,c,d$, and $ P(e)=4$ for some integer $ e$. Consider the polynomial $ Q(x)=4-P(x+e)$: Then $ Q(0)=0$, and the four integers $ x_1=a-e$, $ x_2=b-e$, $ x_3=c-e$, and $ x_4=d-e$ satisfy $ Q(x_i)=2$ for $ i=1,2,3,4$. Since $ Q(0)=0$, we have $ Q(x)=x*R(x)$ for some integer polynomial $ R(x)$. Since $ x-y$ divides $ Q(x)-Q(y)$, we have $ x_i-0$ divides $ Q(x_i)-Q(0)=2$ for $ i=1,2,3,4$. This implies that the $ x_i$ are a permutation of $ 2,1,-1,-2$. Then $ R(2)=1$ and $ R(-2)=-1$, and $ 4=2-(-2)$ must divide $ R(2)-R(-2)=2$. Contradiction. Hence $ n\le4$.

Under the notations above, it follows $ P(x) = (x-a)(x-b)(x-c)(x-d)T(x) + 2$. But then $ 4 = P(e) = (e-a)(e-b)(e-c)(e-d)T(e) + 2$, so $ |(e-a)(e-b)(e-c)(e-d)| \leq 2$. However, the absolute value of the product of four distinct not-null integers is at least $ 4$.

Suppose that, for a given n, there exists such a polynomial. We define Q(x) as P(x)-2 for simplicity. We know Q(x) has n integer zeros, so we write: Q(x)=(x-x1)(x-x2)....(x-xn)*R(x) We want to find an integer x such that Q(x)=2, so since each of {x-x1, x-x2, ..., x-xn} is an integer, so is R(x). We also know that each of {x-x1, x-x2, ..., x-xn, R(x)} has to divide 2, and that each of {x-x1, x-x2, ..., x-xn} is distinct, but 2 can be written as a product of at most 3 different integers (e.g. (-2)*1*(-1)) so n<=3. Now we need a construction for every n<=3, and that's not hard. For n=3: Q(x)=(x-1)(x+1)(x-2) For n=2: Q(x)=-2*(x-1)*(x+1) For n=1: Q(x)=x. Therefore, n=4.

We claim the answer is $n=4$. First, consider the polynomial $(x-1)(x-3)(x-4)+2$. It equals $2$ for the $3$ integers $1,3,4$ and it takes on the value of $4$ at $x=2$. Thus, $n>3$. Now, suppose $n\ge4$ and the property is false. Let $P(x)$ be a polynomial for which the property fails. Then, $P(x)=\alpha(x-r_1)(x-r_2)\cdots(x-r_n)+2$ where $r_1,\ldots,r_n$ are distinct integers. Since the property fails, there is some integer $m$ for which $P(m)=4$. Then, $2=\alpha(m-r_1)(m-r_2)\cdots(m-r_n)$. It follows $|m-r_i|\in\{1,2\}$ for all $i$. Indeed, at most $1$ of them can be $2$, so at least three are $1$. Hence, there exist $i\ne j$ for which $m-r_i=m-r_j$, contradicting $r_i\ne r_j$. Therefore, the property never fails for $n=4$, as desired. $\blacksquare$