Does there exist two non-constant polynomials $f(x),g(x)\in\mathbb Z[x]$ such that for all integers $m,n$, gcd$(f(m),g(n))=1$?

There do not exist such polynomials which are in addition monic, and I would be surprised if this restriction turned out to be fundamental.

Assume that $f, g$ is a monic counterexample. In particular, $\gcd(f(x), g(x)) = 1$ in $\mathbb{Z}[x]$. If $f$ has repeated roots we can replace it with $\frac{f}{\gcd(f, f')}$ and similarly for $g$, so we may assume WLOG that $f$ and $g$ have no repeated roots and share no roots, so that the product $fg$ has no repeated roots.

The key tool is the following weaker version of the Chebotarev density theorem.

Theorem (Frobenius): Let $q(x) \in \mathbb{Z}[x]$ be a monic polynomial with no repeated roots. Then the proportion of primes $p$ for which the factorization of $q(x) \bmod p$ has multiset of degrees $(d_1, d_2, ..., d_n)$ is precisely the proportion of elements of the Galois group $G$ of the splitting field $K$ of $q(x)$ which have cycle type $(d_1, d_2, ..., d_n)$ acting on the roots of $q(x)$.

Corollary: The proportion of primes $p$ for which $q(x) \bmod p$ is a product of linear factors is $\frac{1}{|G|}$; in particular, infinitely many such primes exist; in particular, at least one such prime exists.

Now apply the corollary to $q = fg$. We conclude that there is a prime $p$ such that $f(x)$ and $g(x)$ both split into linear factors $\bmod p$; in particular, the set of integers $n$ for which $f(n) \equiv 0 \bmod p$ and the set of integers $m$ for which $g(m) \equiv 0 \bmod p$ contain arithmetic progressions, so by picking suitably large $n$ and $m$ the conclusion follows.