Solution:

The required polynomials are all polynomials of an even degree $d \geq 2$, and all polynomials of odd degree $d \geq 3$ with negative leading coefficient.

Part I. We begin by showing that any (non-constant) polynomial $S(x)$ not listed above is not $(A, B)$-nice for some pair $(A, B)$ with either $|A|=|B|=2$, or $|A|=|B|=3$.

If $S(x)$ is linear, then so are all the polynomials appearing on the board. Therefore, none of them will be $(A, B)$-nice, say, for $A=\{1,2,3\}$ and $B=\{1,2,4\}$, as desired.

Otherwise, $\operatorname{deg} S=d \geq 3$ is odd, and the leading coefficient is positive. In this case, we make use of the following technical fact, whose proof is presented at the end of the solution.

Claim. There exists a positive constant $T$ such that $S(x)$ satisfies the following condition:
$$S(b)-S(a) \geq b-a \quad \text{ whenever } \quad b-a \geq T$$
Fix a constant $T$ provided by the Claim. Then, an immediate check shows that all newly appearing polynomials on the board also satisfy $(*)$ (with the same value of $T$ ). Therefore, none of them will be $(A, B)$-nice, say, for $A=\{0, T\}$ and $B=\{0, T / 2\}$, as desired.

Part II. We show that the polynomials listed in the Answer satisfy the requirements. We will show that for any $a_{1}<a_{2}<\cdots<a_{n}$ and any $b_{1} \leq b_{2} \leq \cdots \leq b_{n}$ there exists a polynomial $f(x)$ satisfying $f\left(a_{i}\right)=b_{\sigma(i)}$ for all $i=1,2, \ldots, n$, where $\sigma$ is some permutation.

The proof goes by induction on $n \geq 2$. It is based on the following two lemmas, first of which is merely the base case $n=2$; the proofs of the lemmas are also at the end of the solution.

Lemma 1. For any $a_{1}<a_{2}$ and any $b_{1}, b_{2}$ one can write down on the board a polynomial $F(x)$ satisfying $F\left(a_{i}\right)=b_{i}, i=1,2$.

Lemma 2. For any distinct numbers $a_{1}<a_{2}<\cdots<a_{n}$ one can produce a polynomial $F(x)$ on the board such that the list $F\left(a_{1}\right), F\left(a_{2}\right), \ldots, F\left(a_{n}\right)$ contains exactly $n-1$ distinct numbers, and $F\left(a_{1}\right)=F\left(a_{2}\right)$.

Now, in order to perform the inductive step, we may replace the polynomial $S(x)$ with its shifted copy $S(C+x)$ so that the values $S\left(a_{i}\right)$ are pairwise distinct. Applying Lemma 2 , we get a polynomial $f(x)$ such that only two among the numbers $c_{i}=f\left(a_{i}\right)$ coincide, namely $c_{1}$ and $c_{2}$. Now apply Lemma 1 to get a polynomial $g(x)$ such that $g\left(a_{1}\right)=b_{1}$ and $g\left(a_{2}\right)=b_{2}$. Apply the inductive hypothesis in order to obtain a polynomial $h(x)$ satisfying $h\left(c_{i}\right)=b_{i}-g\left(a_{i}\right)$ for all $i=2,3, \ldots, n$. Then the polynomial $h(f(x))+g(x)$ is a desired one; indeed, we have $h\left(f\left(a_{i}\right)\right)+g\left(a_{i}\right)=h\left(c_{i}\right)+g\left(a_{i}\right)=b_{i}$ for all $i=2,3, \ldots, n$, and finally $h\left(f\left(a_{1}\right)\right)+g\left(a_{1}\right)=$ $h\left(c_{1}\right)+g\left(a_{1}\right)=b_{2}-g\left(a_{2}\right)+g\left(a_{1}\right)=b_{1}$.

It remains to prove the Claim and the two Lemmas.

Proof of the Claim. There exists some segment $\Delta=\left[\alpha', \beta'\right]$ such that $S(x)$ is monotone increasing outside that segment. Now one can choose $\alpha \leq \alpha'$ and $\beta \geq \beta'$ such that $S(\alpha)<\min _{x \in \Delta} S(x)$ and $S(\beta)>\max _{x \in \Delta} S(x)$. Therefore, for any $x, y, z$ with $x \leq \alpha \leq y \leq \beta \leq z$ we get $S(x) \leq S(\alpha) \leq S(y) \leq S(\beta) \leq S(z)$.

We may decrease $\alpha$ and increase $\beta$ (preserving the condition above) so that, in addition, $S'(x)>3$ for all $x \notin[\alpha, \beta]$. Now we claim that the number $T=3(\beta-\alpha)$ fits the bill.

Indeed, take any $a$ and $b$ with $b-a \geq T$. Even if the segment $[a, b]$ crosses $[\alpha, \beta]$, there still is a segment $\left[a', b'\right] \subseteq[a, b] \backslash(\alpha, \beta)$ of length $b'-a' \geq(b-a) / 3$. Then
$$S(b)-S(a) \geq S\left(b'\right)-S\left(a'\right)=\left(b'-a'\right) \cdot S'(\xi) \geq 3\left(b'-a'\right) \geq b-a$$
for some $\xi \in\left(a', b'\right)$.

Proof of Lemma 1. If $S(x)$ has an even degree, then the polynomial $T(x)=S\left(x+a_{2}\right)-S\left(x+a_{1}\right)$ has an odd degree, hence there exists $x_{0}$ with $T\left(x_{0}\right)=S\left(x_{0}+a_{2}\right)-S\left(x_{0}+a_{1}\right)=b_{2}-b_{1}$. Setting $G(x)=S\left(x+x_{0}\right)$, we see that $G\left(a_{2}\right)-G\left(a_{1}\right)=b_{2}-b_{1}$, so a suitable shift $F(x)=G(x)+\left(b_{1}-G\left(a_{1}\right)\right)$ fits the bill.

Assume now that $S(x)$ has odd degree and a negative leading coefficient. Notice that the polynomial $S^{2}(x):=S(S(x))$ has an odd degree and a positive leading coefficient. So, the polynomial $S^{2}\left(x+a_{2}\right)-S^{2}\left(x+a_{1}\right)$ attains all sufficiently large positive values, while $S\left(x+a_{2}\right)-S\left(x+a_{1}\right)$ attains all sufficiently large negative values. Therefore, the two-variable polynomial $S^{2}\left(x+a_{2}\right)-S^{2}\left(x+a_{1}\right)+S\left(y+a_{2}\right)-S\left(y+a_{1}\right)$ attains all real values; in particular, there exist $x_{0}$ and $y_{0}$ with $S^{2}\left(x_{0}+a_{2}\right)+S\left(y_{0}+a_{2}\right)-S^{2}\left(x_{0}+a_{1}\right)-S\left(y_{0}+a_{1}\right)=b_{2}-b_{1}$. Setting $G(x)=S^{2}\left(x+x_{0}\right)+S\left(x+y_{0}\right)$, we see that $G\left(a_{2}\right)-G\left(a_{1}\right)=b_{2}-b_{1}$, so a suitable shift of $G$ fits the bill.

Proof of Lemma 2. Let $\Delta$ denote the segment $\left[a_{1} ; a_{n}\right]$. We modify the proof of Lemma 1 in order to obtain a polynomial $F$ convex (or concave) on $\Delta$ such that $F\left(a_{1}\right)=F\left(a_{2}\right)$; then $F$ is a desired polynomial. Say that a polynomial $H(x)$ is good if $H$ is convex on $\Delta$.

If $\operatorname{deg} S$ is even, and its leading coefficient is positive, then $S(x+c)$ is good for all sufficiently large negative $c$, and $S\left(a_{2}+c\right)-S\left(a_{1}+c\right)$ attains all sufficiently large negative values for such $c$. Similarly, $S(x+c)$ is good for all sufficiently large positive $c$, and $S\left(a_{2}+c\right)-S\left(a_{1}+c\right)$ attains all sufficiently large positive values for such $c$. Therefore, there exist large $c_{1}<0<c_{2}$ such that $S\left(x+c_{1}\right)+S\left(x+c_{2}\right)$ is a desired polynomial. If the leading coefficient of $H$ is negative, we similarly find a desired polynomial which is concave on $\Delta$.

If $\operatorname{deg} S \geq 3$ is odd (and the leading coefficient is negative), then $S(x+c)$ is good for all sufficiently large negative $c$, and $S\left(a_{2}+c\right)-S\left(a_{1}+c\right)$ attains all sufficiently large negative values for such $c$. Similarly, $S^{2}(x+c)$ is good for all sufficiently large positive $c$, and $S^{2}\left(a_{2}+c\right)-S^{2}\left(a_{1}+c\right)$ attains all sufficiently large positive values for such $c$. Therefore, there exist large $c_{1}<0<c_{2}$ such that $S\left(x+c_{1}\right)+S^{2}\left(x+c_{2}\right)$ is a desired polynomial.