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$