Obviously, the degree of such a polynomial must be at least $2$. If the degree were equal to $2$, this polynomial would have the form of
$$p(x) = x^2 + a x + b = (x^2 + 1) + a x + (b - 1).$$
When dividing by $x^2 + 1$ the remainder is $2$, and $a x + (b - 1) = 2$ implies $a = 0$ and $b = 3$. But when we divide $p(x) = x^2 + 3 = (x - 1)(x + 1) + 4$ by $x + 1$ the remainder cannot be $1$. We can prove this by calculating $p(-1) = 4$, since $p(-1)$ is precisely the remainder obtained when dividing $p(x)$ by $x + 1$.

We conclude that the degree of our polynomial is at least $3$. Let
$$p(x) = x^3 + a x^2 + b x + c = (x + a)(x^2 + 1) + (b - 1)x + c - a.$$
Again, we have $(b-1)x + c - a = 2$. Hence $b = 1$, $c = a + 2$. From
$$p(x) = x^3 + a x^2 + x + a + 2 = (x + 1)(x^2 + (a - 1)x + 2 - a) + 2a,$$
we find $2a = 1$ (we can also deduce this from $1 = p(-1) = -1 - a - 1 + a + 2$). The polynomial is $p(x) = x^3 + \frac{1}{2}x^2 + x + \frac{5}{2}$.