Solutions to the functional equation $f(f(x))=f(x+1)$

There are no other polynomial solutions - if $f$ has degree $n$, then $f(f(x))$ has degree $n^2$, which is greater than $n$ if $n > 1$. And if $f$ has degree of at most $1$, then $f(x) = ax + b$, and we can find that solutions are only $a = 0$ and $a = 1, b = 1$ - which corresponds to $f(x) = c$ and $f(x) = x + 1$.

There are many discontinuous solutions even without AC. For example, $$f(x) = \begin{cases}0,\ x \in \mathbb{Z}\\ \frac{1}{2}, x \notin \mathbb{Z} \end{cases}$$.

There are also some other continuous solution. For example, $f(x + n) = |x|$ where $n \in \mathbb{Z}$ and $-\frac{1}{2} \leq x < \frac{1}{2}$ (any number has unique such representation): $f(f(x + n)) = f(x) = x$ and $f(x + n + 1) = x$. Alternative form of the same function: $f(x) = \rho(x, \mathbb Z) = \min\limits_{n \in \mathbb Z} |x - n|$.

There are an infinite number of non-continuous solutions which can be created by combining the two solutions you gave. For example, define $A_k$ as the set of algebraic numbers of degree $k$ or less. That is, $A_k$ is the set of algebraic numbers whose minimal polynomial has degree $k$ or less. Now, if $\alpha\in A_k$ then $\alpha+1\in A_k$ and if $\alpha\not\in A_k$ then $\alpha+1\not\in A_k$. Now, define

$$f(x)=\begin{cases} x+1 & x\in A_k \\ c & x \in \mathbb{R}/A_k \end{cases}$$

(for any constant $c$). For any particular $x$ we have

$$f(x)\in A_k \Leftrightarrow x\in A_k$$

Thus, $f(x)$ satisfies the functional equation.