There are two such functions: $f(n) = n + 1$ for all $n \in Z_{\ge 0}$, and
$$f(n) = \begin{cases} n+1, & n \equiv 0 \pmod 4 \text{ or } n \equiv 2 \pmod 4, \\ n+5, & n \equiv 1 \pmod 4, \\ n-3, & n \equiv 3 \pmod 4, \end{cases} \quad \text{for all } n \in Z_{\ge 0}.$$
Throughout all the solutions, we write $h^k(x)$ to abbreviate the $k$th iteration of function $h$, so $h^0$ is the identity function, and $h^k(x) = h(\dots h(x)\dots)$ for $k \ge 1$.

To start, we get from $(*)$ that
$$f^{4}(n) = f(f^{3}(n)) = f(f(n+1)+1) \text{ and } f^{4}(n+1) = f^{3}(f(n+1)) = f(f(n+1)+1)+1,$$
thus
$$f^{4}(n) + 1 = f^{4}(n+1) \qquad (2)$$

I. Let us denote by $R_i$ the range of $f^i$; note that $R_0 = Z_{\ge 0}$ since $f^0$ is the identity function. Obviously, $R_0 \supseteq R_1 \supseteq \dots$. Next, from (2) we get that if $a \in R_4$ then also $a+1 \in R_4$. This implies that $Z_{\ge 0} \setminus R_4$ -- and hence $Z_{\ge 0} \setminus R_1$ -- is finite. In particular, $R_1$ is unbounded.

Assume that $f(m) = f(n)$ for some distinct $m$ and $n$. Then from $(*)$ we obtain $f(m+1) = f(n+1)$; by an easy induction we then get that $f(m+c) = f(n+c)$ for every $c \ge 0$. So the function $f(k)$ is periodic with $|m-n|$ for $k \ge m$, and thus $R_1$ should be bounded, which is false. So $f$ is injective.

II. Denote now $S_i = R_{i-1} \setminus R_i$; all these sets are finite for $i \le 4$. On the other hand, by the injectivity we have $n \in S_i \Leftrightarrow f(n) \in S_{i+1}$. By the injectivity again, $f$ implements a bijection between $S_i$ and $S_{i+1}$, thus $|S_1| = \dots$; denote this common cardinality by $k$. If $0 \in R_3$ then $0 = f(f(f(n)))$ for some $n$, thus from $(*)$ we get $f(n+1) = -1$ which is impossible. Therefore $0 \in R_0 \setminus R_3 = S_1 \cup S_2 \cup S_3$, thus $k \ge 1$.

Next, let us describe the elements $b$ of $R_0 \setminus R_3 = S_1 \cup S_2 \cup S_3$. We claim that each such element satisfies at least one of three conditions (i) $b = 0$, (ii) $b = f(0) + 1$, and (iii) $b - 1 \in S_1$. Otherwise $b - 1 \in Z_{\ge 0}$, and there exists some $n > 0$ such that $f(n) = b - 1$; but then $f^3(n - 1) = f(n) + 1 = b$, so $b \in R_3$.

This yields
$$3k = |S_1 \cup S_2 \cup S_3| \le 1 + 1 + |S_1| = k + 2,$$
or $k \le 1$. Therefore $k = 1$, and the inequality above comes to equality. So we have $S_1 = \{a\}$, $S_2 = \{f(a)\}$, and $S_3 = \{f^2(a)\}$ for some $a \in Z_{\ge 0}$, and each one of the three options (i), (ii) and (iii) should be realized exactly once, which means that
$$\{a, f(a), f^2(a)\} = \{0, a+1, f(0)+1\}. \qquad (3)$$

III. From (3), we get $a + 1 \in \{f(a), f^2(a)\}$ (the case $a + 1 = a$ is impossible). If $a + 1 = f^2(a)$ then we have $f(a + 1) = f^3(a) = f(a + 1) + 1$ which is absurd. Therefore
$$f(a) = a + 1. \qquad (4)$$

Next, again from (3) we have $0 \in \{a, f^2(a)\}$. Let us consider these two cases separately.

Case 1. Assume that $a = 0$, then $f(0) = f(a) = a + 1 = 1$. Also from (3) we get $f(1) = f^2(a) = f(0) + 1 = 2$. Now, let us show that $f(n) = n + 1$ by induction on $n$; the base cases $n \le 1$ are established. Next, if $n \ge 2$ then the induction hypothesis implies
$$n + 1 = f(n - 1) + 1 = f^3(n - 2) = f^2(n - 1) = f(n),$$
establishing the step. In this case we have obtained the first of two answers; checking that it satisfies $(*)$ is straightforward.

Case 2. Assume now that $f^2(a) = 0$; then by (3) we get $a = f(0)+1$. By (4) we get $f(a) = a + 1$, then $f(0) = f^3(a) = f(a+1) + 1 = 1$, hence $a = f(0) + 1 = 2$ and $f(2) = 3$ by (4). To summarize,
$$f(0) = 1, \quad f(2) = 3, \quad f(3) = 0.$$
Now let us prove by induction on $m$ that (1) holds for all $n = 4k, 4k+2, 4k+3$ with $k \le m$ and for all $n = 4k+1$ with $k < m$. The base case $m = 0$ is established above. For the step, assume that $m \ge 1$. From $(*)$ we get $f^3(4m-3) = f(4m-2)+1 = 4m$. Next, by (2) we have
$$f(4m) = f^4(4m - 3) = f^4(4m - 4) + 1 = f^3(4m - 3) + 1 = 4m + 1.$$
Then by the induction hypothesis together with $(*)$ we successively obtain
$$\begin{align*} f(4m - 3) &= f^3(4m - 1) = f(4m) + 1 = 4m + 2, \\ f(4m + 2) &= f^3(4m - 4) = f(4m - 3) + 1 = 4m + 3, \\ f(4m + 3) &= f^3(4m - 3) = f(4m - 2) + 1 = 4m, \end{align*}$$
thus finishing the induction step.

Finally, it is straightforward to check that the constructed function works:
$$f^{3}(4k) = 4k + 7 = f(4k + 1) + 1, \quad f^{3}(4k + 1) = 4k + 4 = f(4k + 2) + 1,$$
$$f^{3}(4k + 2) = 4k + 1 = f(4k + 3) + 1, \quad f^{3}(4k + 3) = 4k + 6 = f(4k + 4) + 1.$$