No, there is no such polynomial. Any polynomial $f(x) \in \mathbb{Z}[x]$ with degree greater than $1$ is reducible modulo every prime factor of every value it takes.
For, take any value of $n$ for which $f(n) \neq \pm 1$. (There must exist such $n$ because $f$ can take the values $1$ and $-1$ only finitely many times.) Consider any prime factor $p$ of $f(n)$. Then $f(n) \equiv 0 \mod p$, which means that $f$ is reducible in $\mathbb{F}_p[x]$: it is divisible by the polynomial $x-n$.
Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 3 \pmod 4} $$
Lemma: $$ (-p|q) = (q|p). $$
Lemma: If $$ a^2 + p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$
Let $$ F_1 = 4 + p, $$
$$ F_2 = 4 F_1^2 + p, $$
$$ F_3 = 4 F_1^2 F_2^2 + p, $$
$$ F_4 = 4 F_1^2 F_2^2 F_3^2 + p, $$
$$ F_5 = 4 F_1^2 F_2^2 F_3^2 F_4^2 + p, $$
and so on.
These are all of the form $a^2 + p$ and are odd, so the only primes than can be factors are quadratic residues for $p.$ Next, all the $F_j$ are prime to $p$ itself. Finally, these are all coprime. So, however they factor, we get an infinite list of primes that are quadratic residues of $p.$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 1 \pmod 4} $$
Lemma: $$ (p|q) = (q|p). $$
Lemma: If $$ a^2 - p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$
FIND an even square $$ W = 4^k = \left( 2^k \right)^2 $$ such that
$$ \color{magenta}{ W > p.} $$
Let $$ F_1 = W - p, $$
$$ F_2 = W F_1^2 - p, $$
$$ F_3 = W F_1^2 F_2^2 - p, $$
$$ F_4 = W F_1^2 F_2^2 F_3^2 - p, $$
$$ F_5 = W F_1^2 F_2^2 F_3^2 F_4^2 - p, $$
and so on. As $p \equiv 1 \pmod 4$ and $W \equiv 0 \pmod 4,$ we know $W - p \equiv 3 \pmod 4 $ and so $W-p \geq 3. $ So the $F_j$ are larger than $1$ and strictly increasing.
These are all of the form $a^2 - p$ and are odd, so the only primes than can be factors are quadratic residues for $p.$ Next, all the $F_j$ are prime to $p$ itself. Finally, these are all coprime. So, however they factor, we get an infinite list of primes that are quadratic residues of $p.$
Best Answer
Let $$f(x)= x^3-3x+4$$ It is irreducible and $$Disc(f) = 4(3)^3-27(-4)^2=-18^2$$
Let $k$ be the splitting field of $f\bmod p$. Factorize $$f(x)=\prod_{j=1}^3 (x-a_j)\in k[x]$$ Note that $$Disc(f)^{1/2}=(a_1-a_2)(a_1-a_3)(a_2-a_3)\in k, \qquad Disc(f)=\prod_{i\ne j} (a_i-a_j)$$
And (exlucding the case $p=3$ where $f=(x+1)^3$ is reducible) since we know that $Disc(f)^{1/2}\in \Bbb{F}_p$ iff $p\not\equiv 3\bmod 4$ we get that $f$ is never irreducible when $p\equiv 3\bmod 4$, ie. $f\bmod p$ has a root.