We know that the "lattice" of polynomials formed by $\binom{x}{0}, \binom{x}{1}, \ldots \binom{x}{n}$ (that is, integer combinations of these polynomials) are all polynomials that have degree at most $n$ and are integers at integer points (proof below). So $\frac{f(x)}{m}$ is of this form. Looking at the denominator of the leading coefficient, we see that $m|n!$ and looking at the polynomial $x(x-1)(x-2)\ldots(x-n+1)$, we can see that this necessary condition is also sufficient. The proof of my statement is by induction (of course). It's clear that polynomials of the form $k\cdot \binom{x}{0}$ are the only 0-degree integer-valued polynomials. Hence we're done with our base case. The inductive step involves noting that if $f$ is such a polynomial, then so is $f(x)-f(x-1)$ which is necessarily one lower degree than $f$. Hence $f(x)-f(x-1)$ is of the form $k_0\binom{x}{0}+k_1\binom{x}{1}+\ldots+k_{n-1}\binom{x}{n-1}$, so that $f(x)=C+k_0\binom{x}{1}+k_1\binom{x}{2}+\ldots+k_{n-1}\binom{x}{n}$ with $C$ being an integer. Hence we're done.

Let $m=p_1^{\alpha_1}\ldots p_s^{\alpha_s}$ be the canonical decomposition of $m$. Take $f(x)=(x^{p_1}-x)^{\alpha_1}\ldots(x^{p_s}-x)^{\alpha_s}$. Since the leading coefficient of $f(x)$ is 1, then obviously $\gcd(a_n,\ldots,a_0,m)=1$ holds. It now suffices to show that $m|f(x)$ for all integers $x$. We know that $x^{p_i}-x$ is identical to zero in $\mathbb{Z}/p_i\mathbb{Z}$ and thus $p_i^{\alpha_i}|(x^{p_i}-x)^{\alpha_i}$ for all $x\in\mathbb{Z}$.