We use the notation $f^n : \mathbb{Z} \to \mathbb{Z}, n \in \mathbb{N}$, for the $n$-fold iterate of $f$. Note that
$$f(n + 3) = f(f^3(n)) = f^3(f(n)) = f(n) + 3$$
which, by an easy induction argument implies that
$$f(n + 3k) = f(n) + 3k, \quad \text{for all } n, k \in \mathbb{Z}. \qquad (20)$$

It follows that once we know $f$ for a complete set of mod-3 representatives, such as $\{0, 1, 2\}$, we know all values of $f$. Furthermore, $f$ induces a function $f_3 : \mathbb{Z}_3 \to \mathbb{Z}_3$: just work mod 3 on both the domain and image sides.
Moreover, $f$ cannot fix a residue class mod 3 since if $f(n) = n+3m$, then (20) would imply that $f^2(n) = n + 6m$ and $f^3(n) = n + 9m$, which is inconsistent with the identity $f^3(n) = n + 3$. Thus, $f_3$ is a 3-cycle. Bearing in mind (20), it follows that $f$ is defined either by
$$f(n) = \begin{cases} n + 1 + 3i, & n \equiv 0 \pmod{3}, \\ n + 1 + 3j, & n \equiv 1 \pmod{3}, \\ n + 1 + 3k, & n \equiv 2 \pmod{3}, \end{cases} \qquad (21)$$
or
$$f(n) = \begin{cases} n - 1 + 3i, & n \equiv 0 \pmod{3}, \\ n - 1 + 3j, & n \equiv 1 \pmod{3}, \\ n - 1 + 3k, & n \equiv 2 \pmod{3}, \end{cases} \qquad (22)$$
for some $i, j, k \in \mathbb{Z}$. In fact, the identity $f^3(n) = n + 3$ allows us to compute $k$ in terms of $i, j$ in both cases: in (21), we must have $k = -i - j$ while in (22), we must have $k = 2 - i - j$.
With these equations, it is routine to check that all of these functions give solutions of the desired identity. In fact, this follows in (21) from the fact that $f_3$ is a 3-cycle so when we apply $f$ three times to any given number $n$, we are adding $1+3i, 1+3j$, and $1-3i-3j$ in some order; the proof for (22) is similar.
Note that distinct pairs $(i, j)$ in either (21) or (22) give distinct functions (with $k$ specified as above), and also a function of type (21) never equals a function of type (22) since the associated function $f_3$ is different in both cases (but independent of $i$ and $j$).