Gro-Tsen's solution is elegant. Here's a more elementary solution that doesn't directly use any algebraic number theory. I'll change the polynomials to $f(x)$ and $g(x)$. We'll assume that
$$\gcd(f(n),g(m))=1 \quad\hbox{for all $m,n\in\mathbb N$ } \qquad(*)
$$
and derive a contradiction. We may assume, WLOG, that $f(x)$ and $g(x)$ have no common factors in $\mathbb Q[x]$. We first note that if there is a prime $p$ that divides the resultant $\operatorname{Res}_x(f(x),g(x))$, then $f(x)$ and $g(x)$ have a common root mod $p$, and lifting that root to an integer $n\in\mathbb N$, we find that $p\mid\gcd(f(n),g(n))$, which contradicts $(*)$. More generally, for every integer $m\in\mathbb N$, if there is a prime $p$ dividing $\operatorname{Res}_x\bigl(f(x),g(x+m)\bigr)$, then we can repeat the argument to find an $n\in\mathbb N$ such that $p\mid\gcd(f(n),g(n+m))$, again contradicting $(*)$. To summarize, we've proven that
$$
(*)\quad\Longrightarrow\quad\operatorname{Res}_x\bigl(f(x),g(x+m)\bigr)=\pm1\quad\hbox{for every $m\in\mathbb N$.}$$

This means that the polynomial
$$\operatorname{Res}_x\bigl(f(x),g(x+y)\bigr)^2\in\mathbb Q[y]$$
is identically equal to $1$ for every $y\in\mathbb N$, which means that it's identically equal to $1$ as a polynomial. Taking square roots, for one of the choices $\epsilon\in\{\pm1\}$, we have proven that
$$
\operatorname{Res}_x\bigl(f(x),g(x+y)\bigr) = \epsilon.
$$
Using standard formal properties of the resultant over any ring (in our case, the ring $\mathbb Q[y]$), there are polynomials $A(x,y),B(x,y)\in\mathbb Q[x,y]$ satisfying
$$
A(x,y)f(x) + B(x,y)g(x+y) = \epsilon \quad\text{in the polynomial ring $\mathbb Q[x,y]$.}
$$
We are assuming that $f(x)$ is not a constant polynomial, so it has a root $x_0$ living in some finite extension $K$ of $\mathbb Q$. (This admittedly uses a little bit of field theory.) Substituting $x=x_0$, we find that
$$
B(x_0,y)g(x_0+y) = 1 \quad\text{in the polynomial ring $K[y]$.}
$$
It follows that $\deg_yg(x_0+y)=1$ in $K[y]$, and thus that $\deg_xg(x)=1$ in $\mathbb Q[x]$. Reversing the roles of $f$ and $g$ gives $\deg_xf(x)=1$. We have thus reduced to the case that $f$ and $g$ are non-constant linear polynomials, in which case $f$ and $g$ have roots modulo $p$ for all but finitely many primes $p$.