If $B = \{i: P(a_i) = -1\}$, then $P(z)+1$ is divisible by $Q(z) = \prod_{i \in B} (z - a_i)$. We may assume $\text{card}(B) \ge (d+1)/2$ (otherwise replace $P$ by $-P$. Now if $i \in \{1,\ldots,d+1\} \backslash B$, $P(a_i) = 1$ so $Q(a_i)$ divides $2$, so $Q(a_i) \in \{-2,-1,1,2\}$. So each $a_i - a_j$ for $j \in B$ is in $\{-2,-1,1,2\}$, and at most one can be $\pm 2$. In particular, $\text{card}(B) \le 3$. Moreover, if $\text{card}(B) = 3$ there is at most one possible value for $a_i$, namely $0$. This reduces us to a small number of possible cases, which can be checked individually.
EDIT: One such case is $P(x) = 1 + (x+1)(x-2)$, where $P(x) = 1,-1,-1,1$ for $x=-1,0,1,2$, do $d = 3$ and $\deg P = 2$.