Suppose that $P, Q \in \mathbb{Z}[x]$ satisfy the given requirement. Step by step we will draw some conclusions.

Step 1. $\operatorname{deg} P \geq 1, \operatorname{deg} Q \geq 1$.
Suppose, on the contrary, that one of $P, Q$ were a constant polynomial $c$.
1. If $P(x)=c\ (\forall x \in \mathbb{Z})$, then
$$x_{n} \in\{2016, c, Q(c)\} \quad \forall n \geq 0.$$
2. If $Q(x)=c\ (\forall x \in \mathbb{Z})$, then
$$x_{n} \in\{2016, P(2016), c, P(c)\} \quad \forall n \geq 0.$$
In both cases, the requirement "every positive integer is a divisor of a certain nonzero term of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$" couldn't be satisfied. Hence, $\operatorname{deg} P \geq 1, \operatorname{deg} Q \geq 1$.

Step 2. $\operatorname{deg} Q=1$.
Suppose, on the contrary, that $\operatorname{deg} Q>1$.
By Step 1, $\operatorname{deg} P \geq 1$, so there exist positive numbers $M$ and $k \geq 1$ such that $k|P(x)| \geq|x|$ for all $x \in \mathbb{Z}$ with $|x| \geq M$. In particular, $\lim _{|x| \rightarrow \infty}|P(x)|= \infty$.
But $\operatorname{deg} Q>1$, which implies that
$$\lim _{|x| \rightarrow \infty} \frac{|Q(x)|}{|x|}=\infty ;$$
therefore, if $N \in(M, \infty)$ is chosen large enough, then we have:
$$|Q(x)|>|x|$$
and
$$|Q(P(x))|>2 k|P(x)|=k|P(x)|+k|P(x)| \geq k|P(x)|+|x|$$
when $|x| \geq N$.
Now, in accordance with the given requirement, $\lim _{n \rightarrow \infty} \max _{0 \leq \ell \leq 2 n}\left|x_{\ell}\right|=\infty$. Further, for large $n$, let $0 \leq i=i(n) \leq 2 n$ be an index such that
$$\left|x_{i}\right|=\max _{0 \leq \ell \leq 2 n}\left|x_{\ell}\right|>N.$$
If $i$ were odd, say $i=2 j-1$, then we would get
$$\left|x_{2 j}\right|=\left|Q\left(x_{2 j-1}\right)\right|>\left|x_{2 j-1}\right|=\max _{0 \leq \ell \leq 2 n}\left|x_{\ell}\right|,$$
a contradiction (since $2 j \leq 2 n$ ). So, $i$ should be even (when $n$ is large enough), say $i=2 j$. For such a $j$, take $m=\left|x_{2 j+2}-x_{2 j}\right|$. Then
$$m=\left|Q\left(P\left(x_{2 j}\right)\right)-x_{2 j}\right| \geq\left|Q\left(P\left(x_{2 j}\right)\right)\right|-\left|x_{2 j}\right|>k\left|P\left(x_{2 j}\right)\right| \geq\left|x_{2 j}\right|$$
and $m>k\left|P\left(x_{2 j}\right)\right| \geq\left|P\left(x_{2 j}\right)\right|=\left|x_{2 j+1}\right|$. Therefore, among the first $2 j+2$ terms $x_{0}, x_{1}, \ldots, x_{2 j}, x_{2 j+1}$, there do not exist any term which is nonzero and which is divisible by $m$. It should also be noted here that $x_{2 j} x_{2 j+1} \neq 0$ (since $\left|x_{2 j+1}\right|=\left|P\left(x_{2 j}\right)\right| \geq \frac{\left|x_{2 j}\right|}{k}>\frac{N}{k}>0$ ). Hence, neither $x_{2 j}$ nor $x_{2 j+1}$ is divisible by $m$.
On the other hand,
$$\left(x_{2 \ell+2}-x_{2 \ell}\right) \mid\left(Q\left(P\left(x_{2 \ell+2}\right)\right)-Q\left(P\left(x_{2 \ell}\right)\right)\right)=x_{2 \ell+4}-x_{2 \ell+2}$$
and
$$\left(x_{2 \ell+2}-x_{2 \ell}\right) \mid\left(P\left(x_{2 \ell+2}\right)-P\left(x_{2 \ell}\right)\right)=x_{2 \ell+3}-x_{2 \ell+1}.$$
Thus, if $\ell \geq j$, then $x_{2 \ell+2}-x_{2 \ell}$ and $x_{2 \ell+3}-x_{2 \ell+1}$ are both divisible by $m=\left|x_{2 j+2}-x_{2 j}\right|$. But, as we have shown above, neither $x_{2 j}$ nor $x_{2 j+1}$ is divisible by $m$. It follows that neither $x_{2 \ell+2}$ nor $x_{2 \ell+3}$ is divisible by $m$ when $\ell \geq j$.
Therefore, $m$ could not be a divisor of any nonzero term of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$, a contradiction again! So, $\operatorname{deg} Q=1$.

Step 3. $\operatorname{deg} P=1$.
The proof is similar to that in Step 2.

Step 4. Now $P(x)=a x+b, Q(x)=c x+d$ with $a, b, c, d \in \mathbb{Z}$ and $a b \neq 0$. We will prove that $a c=1$. By definition,
$$\left\{ \begin{array}{l} x_{2 n+1}=a x_{2 n}+b \\ x_{2 n+2}=c x_{2 n+1}+d \end{array} \quad \forall n \geq 0 .\right.$$
Hence, $x_{2 n+2}=a c x_{2 n}+b c+d$ and $x_{2 n+3}=a c x_{2 n+1}+a d+b$ for all $n \geq 0$. These 2 sub-sequences share a common recurrence relation of the form $y_{n+1}=r y_{n}+s$ with $s \in \mathbb{Z}, r=a c$.
Suppose, on the contrary, that $r \neq 1$. Then
$$y_{n}=r^{n} y_{0}+s \frac{r^{n}-1}{r-1} \quad \forall n \geq 0.$$
If $r=-1$, then $y_{n} \in\left\{y_{0},-y_{0}+s\right\}(\forall n)$; therefore, the given requirement could not be satisfied. So, $|r|>1$.
The requirement implies that one of the above-mentioned 2 sub-sequences has the following property: for each $q \in \mathbb{N}_{0}$ there is an $n=n(q) \in \mathbb{N}_{0}$ such that $r^{q} \mid y_{n} \neq 0$. Of course, $n \rightarrow \infty$ as $q \rightarrow \infty$. Moreover,
$$r^{\min \{q, n\}} \left\lvert\,\left(y_{n}-r^{n} y_{0}\right)=s \frac{r^{n}-1}{r-1} .\right.$$
Since $\operatorname{gcd}\left(r, \frac{r^{n}-1}{r-1}\right)=1$, it follows that $r^{\min \{q, n\}} \mid s$ (for all $q$ ). But $|r|>1$ and $\min \{q, n\} \rightarrow \infty$ as $q \rightarrow \infty$, we see that $s=0$. Hence, $y_{n}=r^{n} y_{0}(\forall n)$,
and therefore, the requirement could not be satisfied. This contradiction shows that $r=a c=1$.

Step 5. Finally, $P(x)= \pm x+b, Q(x)= \pm x+d$ where $b, d \in \mathbb{Z}$ are to be found. We have to consider two cases:
- $P(x)=x+b$ and $Q(x)=x+d$ with $b, d \in \mathbb{Z}$. In this case, by induction, we can show that
$$x_{2 n}=2016+n(b+d) \text{ and } x_{2 n+1}=2016+b+n(b+d) \quad \forall n \geq 0.$$
So, a necessity condition for the requirement to be satisfied is $b+d \neq 0$. Under this condition, the requirement says that for each $m \in \mathbb{N}$ one of the linear congruences
$$(b+d) x \equiv-2016(\bmod m),(b+d) x \equiv-(2016+b)(\bmod m)$$
has (infinitely many) solutions $x=n$ in $\mathbb{N}_{0}$. Equivalently,
$\operatorname{gcd}(b+d, m) \mid 2016$ or $\operatorname{gcd}(b+d, m) \mid(2016+b)$ for each $m \in \mathbb{N}$.
It suffices to consider $m=|b+d|$ and obtain the condition:
$$(b+d) \mid 2016 \text{ or }(b+d) \mid(2016+b), \text{ where } b+d \neq 0$$
- $P(x)=-x+b$ and $Q(x)=-x+d$ with $b, d \in \mathbb{Z}$. In almost the same manner, we see that the requirement is satisfied if and only if
$$(b-d) \mid 2016 \text{ or }(b-d) \mid(-2016+b), \text{ where } b-d \neq 0.$$

Remark. We are going to give here another proof of the conclusions in Steps 2-3 (the proof of that in Step 1 and Steps 4-5 will be the same). We need the following lemma.

Lemma. Let $a \in \mathbb{Z}$ and $T \in \mathbb{Z}[x]$ be given. A sequence ( $y_{n}$ ) is defined as
$$y_{0}=a,\quad y_{n+1}=T\left(y_{n}\right) \quad \forall n \geq 0$$
Suppose that each positive integer $m$ is a divisor of some nonzero term of $\left(y_{n}\right)$. Then $\operatorname{deg} T=1$.

Proof. It is easy to check that any constant polynomial $T$ does not satisfy the given condition. We suppose on the contrary that $\operatorname{deg} T>1$. Then there exists $c>0$ such that $|T(x)|>2|x|$ whenever $|x|>c$.
By assumption, $\lim _{m \rightarrow \infty} \max _{0 \leq \ell \leq m}\left|y_{\ell}\right|=\infty$. Further, let $0 \leq n=n(m) \leq m$ be the smallest index such that $\left|y_{n}\right|=\max _{0 \leq \ell \leq m}\left|y_{\ell}\right|$. Then $n \rightarrow \infty$ as $m \rightarrow \infty$, and $\left|y_{n}\right|>\left|y_{i}\right|$ for all $0 \leq i<n$. Hence, we can choose an $N \in \mathbb{N}$ such that $\left|y_{N}\right|>\max \left\{c,\left|y_{0}\right|,\left|y_{1}\right|, \ldots,\left|y_{N-1}\right|\right\}$. In particular, this implies that
$$\left|y_{N+1}\right|=\left|T\left(y_{N}\right)\right|>2\left|y_{N}\right|.$$
Set $m=\left|y_{N+1}-y_{N}\right|$. Then
$$m \geq\left|y_{N+1}\right|-\left|y_{N}\right|>\left|y_{N}\right|>\max \left\{\left|y_{0}\right|,\left|y_{1}\right|, \ldots,\left|y_{N-1}\right|\right\}.$$
Therefore, $y_{N}$ is not divisible by $m$. Moreover, $m$ is not a divisor of any nonzero term among $y_{0}, y_{1}, \ldots, y_{N-1}$.
On the other hand, $y_{n+1}-y_{n}$ is divisible by $y_{n}-y_{n-1}$ for all $n \geq 1$. So, $y_{n+1}-y_{n}$ is divisible by $m=\left|y_{N+1}-y_{N}\right|$ for all $n \geq N$. It follows that
$$y_{n}-y_{N}=\left(y_{n}-y_{n-1}\right)+\left(y_{n-1}-y_{n-2}\right)+\ldots+\left(y_{N+1}-y_{N}\right)$$
is divisible by $m$ for all $n>N$. But $y_{N}$ is not divisible by $m$, so $y_{n}$ is not divisible by $m$ for all $n>N$, which is a contradiction. This completes the proof of the lemma.

We are now in a position to prove the conclusions of Steps 2-3.
Let $H(x)=P(Q(x))$ and $K(x)=Q(P(x))$. Suppose, on the contrary, that either $\operatorname{deg} P \geq 2$ or $\operatorname{deg} Q \geq 2$. Then $\operatorname{deg} H \geq 2$ and $\operatorname{deg} K \geq 2$ (since, by Step $1, \operatorname{deg} P \geq 1, \operatorname{deg} Q \geq 1$ ).
Consider the sub-sequence $\left(x_{0}, x_{2}, x_{4}, \ldots\right), x_{2(n+1)}=K\left(x_{2 n}\right)$ for all $n \geq 0$. Because $\operatorname{deg} K \geq 2$, the sequence $\left(y_{n}\right)=\left(x_{2 n}\right)$ cannot satisfy the condition given in the lemma. Thus, there exists a positive integer $m$ such that none of $m, 2 m, 3 m, \ldots$ can be a divisor of a certain nonzero term $x_{2 n}$.
This implies that for each $k \in \mathbb{N}$ there exists a nonzero term $x_{2 n_{k}+1}$ divisible by $k m$. Therefore, the sub-sequence
$$\left(x_{1}, x_{3}, x_{5}, \ldots\right), x_{2 n+3}=H\left(x_{2 n+1}\right)$$
(for all $n \geq 0$ ), satisfies the condition given in the lemma. According to this lemma, $\operatorname{deg} H=1$, a contradiction.
This contradiction shows that $\operatorname{deg} P=1, \operatorname{deg} Q=1$.