Freeness of a Z[x]-module Definition: Call a mapping $f: \mathbb{Z} \rightarrow \mathbb{Z}$
a generalized polynomial if for any distinct integers $m$ and $n$
we have $(m - n)|(f(m)-f(n))$.
It is easy to check that polynomial functions $f \in \mathbb{Z}[x]$ are
generalized polynomials, that not all generalized polynomials are polynomials
and that the generalized polynomials form a ring under pointwise addition and
multiplication. Call the latter ring $R$.

Question: Is $R$, viewed as a $\mathbb{Z}[x]$-module, free? 
  And if yes, how does a basis look like?

 A: A basis for $R\cap\mathbb Q[X]$ was described by Carlitz (see the book of Cahen and Chabert "Integer valued polynomials").
The polynomials $\mathrm{LCM}(1,\cdots,n)\binom{X}{n}$ form a basis.
It should be noted that the the ring $R'=\{f:\mathbb N\to\mathbb Z\text{ such that }m-n\mid f(m)-f(n)\text{ for all }m,n\in\mathbb N\}$ is a free $\mathbb Z$-module spanned by the previous polynomials. This result was proved by Rausch.
A: I posted a bunch of comments here, but I thought it would be better to write an answer, instead.
First, I've written up a lot about these functions, and functions with the same condition on  sets $S\subseteq \mathbb Z$. 
If you define $$q_k(x) =  \frac{\operatorname{lcm}(1,2,\dots,k)}{k!}\left(x+ \left\lfloor {\frac{k-1}{2}} \right\rfloor\right)_k$$ then these are rational polynomials in $R$ and they have the property that, for all $n\in\mathbb Z$, $q_k(n)\neq 0$ for only finitely many $k$. So given any infinite sequence $(a_k)_{k\in\mathbb N}$ of integers, we get a unique $f\in R$ defined by:
$$f(n)=\sum_{k} a_kq_k(n)$$
A little harder to prove, but not really hard, is that every $f\in R$ is expressed in this form. Essentially, you find $a_k$ by induction.
This gives an explicit abelian group isomorphism between $R$ and $\mathbb Z^{\mathbb N}\cong\mathbb Z^{\mathbb Z}$.
The proof is essentially using Chinese remainder there inductively to determine $a_k$, to match the values of $f(0),f(1),f(-1),f(2),f(-2),\dots.$ This is why you get the term $\operatorname{lcm}(1,2,\dots,k)$.
This also helps show that $R\cap \mathbb Q[x]$ has the $q_k$ as $\mathbb Z$-generators. Given a polynomial $q(x)\in Q[x]\cap R$ is of degree $d$, if $q(n)=\sum_{k\in N} a_k q_k(n)$ then $p(n)=\sum_{k=0}^{d} a_kq_k(n)$ is another polynomial of degree $d$ which agrees at $d+1$ values, so must agree everywhere.
Side note: $R$ is actually an integral domain, not just a ring. If $f\in R$, then $f$ can be zero only for finitely many values, so $fg=0$ implies $f=0$ or $g=0$. 
Using $R'=\left\{f:\mathbb N\to \mathbb Z\mid \forall n,m: n-m\mid f(n)-f(m)\right\}$, there is a natural ring homomorphism $R\to R'$ be sending $f\in R$ to $f_{\mid\mathbb N}\in R'$. This is $1-1$ since if $f_{\mid\mathbb N} =0$, then $f$ has infinitely many zeros. The map is not onto - it is possible to define $f\in R'$ such that you can't even extend $f$ to $-1$ and keep the divisibliity property.
A: It is not free. Set $f(x) = x(x-1)(x-2)(x-3)/2$.
Claim: $f(x)$ is in $R$. 
Proof: We have
$$\frac{f(x+N)-f(x)}{N} = \frac{N^3+11 N}{2} + (\mbox{an element of } \mathbb{Z}[x,N]).$$
The fraction $(N^3+11N)/2$ is an integer by checking the two possible parities for $N$, and an element of $\mathbb{Z}[x,N]$ is clearly an integer. $\square$
Let $g(x) = 1$. So $x(x-1)(x-2)(x-3) g = 2 f$. In a free $\mathbb{Z}[x]$ module, this would imply that $2$ divided $g$; since $2$ does not divide $g$, this shows that $R$ is not free.
Let me explain this step in more detail. Suppose, for the sake of contradiction, that $h_i$ is a basis for $R$, for $i$ running over some index set $I$. Let $f = \sum_{i \in I} a_i h_i$ and let $g = \sum_{i \in I} b_i h_i$, for $a_i$ and $b_i \in \mathbb{Z}[x]$. Then $2 a_i = x(x-1)(x-2)(x-3) b_i$ for every $i$. In the ring $\mathbb{Z}[x]$, if $2a = x(x-1)(x-2)(x-3) b$ then $2$ divides $b$. Set $b_i = 2 c_i$ for $c_i \in \mathbb{Z}[x]$. Then $\sum c_i h_i$ is an element of $R$ which obeys $2 \sum c_i h_i = g$. 
By the way, this also shows that this is not the direct product of some infinite list of free modules, which I would have considered a more natural guess.
A: Following Todd Trimble's comment and Stefan Kohl's remark, we can show that $R$ is isomorphic to $\mathbf{Z}^{\mathbf{Z}}$ as a $\mathbf{Z}$-module. Since the product of countably many copies of $\mathbf{Z}$ is not free as a $\mathbf{Z}$-module — see this MO question — we deduce that $R$ is not free over $\mathbf{Z}$, which implies in particular that $R$ is not free over $\mathbf{Z}[x]$.
Let us endow $\mathbf{Z}$ with the following well-ordering  : $0, 1, -1, 2, -2, 3, -3\dots$ The map $\phi : \mathbf{Z}^{\mathbf{Z}} \to R$ will have the form $(a_n)_{n \in \mathbf{Z}} \mapsto f$ where $f(n)$ is defined as a finite linear combination of the $a_m$ where $m$ runs trough the indices which are at most $n$ with respect to this well-ordering.
In order to give the idea of the construction, assume we work with functions defined on $\mathbf{N}$ instead of $\mathbf{Z}$, and give $\mathbf{N}$ the usual ordering. Define a map $(a_n)_{n \in \mathbf{N}} \mapsto f$ by putting $f(0)=a_0$, $f(1)=a_1$, $f(2)=a_0+2a_2$, $f(3)=3a_1-2a_0+6a_3$… The coefficients are chosen using the Bézout identity in such a way that the needed congruences hold, e.g. $f(3) \equiv f(0) \pmod{3}$.
In more detail, assume $f(n-k),\ldots,f(n-1)$ have been already defined, and let us define $f(n)$. (We proceed in an analogous way when defining $f(n)$ assuming $f(n+1),\ldots,f(n+k)$ are already defined.) Put $M=\operatorname{lcm}(1,\ldots,k) = p_1^{\alpha_1} \cdots p_r^{\alpha_r}$. We must have $p_i^{\alpha_i} \leq k$ for each $i$. There exist integers $\lambda_1,\ldots,\lambda_r \in \mathbf{Z}$ such that $\lambda_i \equiv 1 \pmod{p_i^{\alpha_i}}$ and $\lambda_i \equiv 0 \pmod{p_j^{\alpha_j}}$ for $j \neq i$. Then we put $f(n) = \sum_{i=1}^r \lambda_i f(n-p_i^{\alpha_i})+M \cdot a_n$. We check that $f(n) \equiv f(n-j) \pmod{j}$ for each $j$, and $f(n)$ is clearly linear with respect to the sequence $(a_n)$.
This defines our linear map $\phi : \mathbf{Z}^{\mathbf{Z}} \to R$. Now, it is not hard to see that $\phi$ is bijective by working backwards, starting from $f \in R$ and defining $a_n$ inductively, starting from $a_0=f(0)$, $a_1=f(1)$ and so on. We have to check the following : if $f \in R$ then using the notations above, we have $f(n) \equiv \sum_{i=1}^r \lambda_i f(n-p_i^{\alpha_i}) \pmod{M}$. Indeed, this holds modulo each $p_i^{\alpha_i}$ using the property of the $\lambda_i$'s and the assumption on $f$.
To sum up, the general picture is that (after fixing the well-ordering of $\mathbf{Z}$ explained above), the $\mathbf{Z}$-module $R$ is the homomorphic image of $\mathbf{Z}^{\mathbf{N}}$ under some infinite lower-triangular matrix
$$
\begin{equation*}
\begin{pmatrix}
1 & 0 & 0 & 0 & \cdots \\
0 & 1 & 0 & 0 &  \\
0 & 1 & 2 & 0 &   \\
3 & -2 & 2 & 6 &  \\
\vdots & & & & \ddots
\end{pmatrix}
\end{equation*}.
$$
