Let $P$ be the set of all positive primes. Let $S$ an arbitrary infinite subset of $P$ satisfying the following assumption: there exists a finite Galois extension $K$ of $\mathbb{Q}$ and a conjugacy class $C\subset \mathrm{Gal}(K/\mathbb{Q})$ such that $P\setminus S$ is exactly the set of primes unramified in $K/\mathbb{Q}$ whose Frobenius conjugacy class is equal to $C$.

Must there exist a non-constant monic polynomial over $\mathbb{Z}$ that is reducible modulo the primes in $S$ and only those primes?

The above assumption is necessary. To see why, take the splitting field of the polynomial and note that the primes modulo which it is reducible are exactly the ramified primes and the unramified primes whose Frobenius conjugacy class does not contain $n$-cycles under the usual embedding of the Galois group into $S_n$ ($n$ is the degree of the polynomial).