Observe that since $f^0(n) = n$ by definition, $f(n) \equiv 0$ is a solution. Now suppose that for some $c \in \mathbb{N}_0$, $f(c) \ge 1$.
As $f(f^{f(c)-1}(n - 2f(c))) = n$ for all $n \ge 2f(c)$, $f$ is onto for all $n \ge 2f(c)$. Therefore $f^m(n) = n + 2m$ for all $n \ge m \ge 2f(c)$.
Since we have $f^{2f(c)}(n) = n + 4f(c)$ and $f^{2f(c)+1}(n) = n + 4f(c) + 2$ for all $n \ge 2f(c)$, it follows that $f(n + 4f(c)) = n + 4f(c) + 2$ for all $n \ge 2f(c)$, in other words, $f(n) = n + 2$ for all $n \ge 6f(c)$.
Let $t$ be the least integer such that $f(n) = n + 2$ for all $n \ge t$. (We have $t \le 6f(c)$). We will show that $f(n) = 0$ for all $n < t$.
Suppose, for the sake of contradiction, that $f(b) = a$ for some $b < t$ and $a \ne 0$. Now suppose that there exists $u < t$ such that $f(u) \ge t$. For clarity, let $f(u) = t+d$ for some $d \ge 0$. Since $f^{f(u)}(u) = u + 2t + 2d$, and $f^{f(u)-1}(f(u)) = f^{t+d-1}(t+d) = 3t + 3d - 2$, we have $f(u) = t+d = u+2$. Since $f(u) \ge t$, $u$ is either $t-2$ or $t-1$. However, if $u = t-1$, $f(t-1)$ will be equal to $(t-1)+2$, which contradicts the minimality of $t$. Thus if such a $u$ exists, then $u = t-2$.
Back to $a, b$, since $t-1 \ge b$, we have $f^a(t-1) = t-1+2a$, but since $t-1 < t$ and $t-1+2a \ge t$, there must be some $0 \le j < a$ such that $f^j(t-1) < t \le f^{j+1}(t-1)$. By the previous paragraph, where $u = f^j(t-1)$, we have $f^j(t-1) = t-2$, and $f^{j+1}(t-1) = t$. Therefore $f^a(t-1) = t+2(a-j-1)$. Therefore $2j = -1$, which is impossible, so we have a contradiction. Hence $f(n) = 0$ for all $n < t$.

$$f(n) = \begin{cases} 0, & n < t, \\ n + 2, & n \ge t, \end{cases}$$
actually satisfies the given condition. If $m < t$, the given condition reduces to $f^0(n) = n$, which is true, while if $m \ge t$, we have $n \ge t$, thus $f^{f(m)}(n) = n+2f(m)$. Hence this function satisfies the given condition, and our proof is complete.

(by Wijit Yangjit)
As in Solution 1, observe that $f(n) \equiv 0$ is a solution, and if for some $c \in \mathbb{N}_0$, we have $f(n) = n + 2$ for all big enough $n$. Define $t$ as in Solution 1.
If for some $n < t$, $f(n) \ge t + 2$, then $f(f(n) - 2) = f(n)$, so $f(n) - 2 + 2f(n) = f^{f(n)}(f(n) - 2) = f^{f(n)}(n) = n + 2f(n)$, so $f(n) = n + 2 < t + 2$, which is a contradiction. Thus $f(n) \le t + 1$ for all $n < t$.
We will prove, by induction, that $f^m(t-1) \le t-2+2m$ for all $m \ge 1$. For $m=1$, $f(t-1) = t+1$ contradicts the minimality of $t$, so $f(t-1) \le t = t-2+(2 \times 1)$.
Now suppose that $f^k(t-1) \le t-2+2k$ for some $t \ge 1$.
If $f^k(t-1) \ge t$, then $f^{k+1}(t-1) = f^k(t-1)+2 \le t-2+2(k+1)$. Else we have $f^k(t-1) < t$, which implies $f^{k+1}(t-1) \le t+1 \le t-2+2(k+1)$ because $k+1 \ge 2$.
Therefore by induction, $f^m(t-1) \le t-2+2m$ for all $m \ge 1$.
Now suppose that $f(n) > 0$ for some $n < t$, we will have $f^{f(n)}(t-1) = t-1+2f(n) > t-2+2f(n)$, which contradicts with the previous paragraph, so $f(n) = 0$ for all $n < t$. We can check our answer as in Solution 1.

As in Solution 1, observe that $f(n) \equiv 0$ is a solution, and if for some $c \in \mathbb{N}_0$, we have $f(n) = n + 2$ for all big enough $n$.
Denote by $P(m,n)$ the statement that $f^{f(m)}(n) = n+2f(m)$. We will show that if $f(x) = f(y) > 0$ then $x = y$. (This will be called property 1.) This is easy: from $P(x,x)$ and $P(y,y)$, $y+2f(y) = f^{f(y)}(y) = f^{f(x)}(x) = x+2f(x)$ where the middle equality is true because $f(x) = f(y) \ge 1$.
We define $t$ as in Solution 1. We want to show that $f(n) = 0$ for all $n < t$. Now suppose for the sake of contradiction that $f(k) \ne 0$ for some $k \le t-1$. From $P(k,t-1)$, $f^{f(k)}(t-1) = t-1+2f(k-1)$, but from $f(n) = n+2$ for all $n \ge t$, $f^{f(k)-1}(t+1) = t+1+2f(k-1)$, so
$$f^{f(k)}(t-1) = f^{f(k)-1}(t+1).$$
Since $f^n(t+1) > 0$ for all $n \ge 0$, using property 1 repeatedly will yield $f(t-1) = t+1$, which contradicts the minimality of $t$. Therefore $f(n) = 0$ for all $n < t$. We can check our answer as in Solution 1.