Does there exist a function $g\in \mathbb{N}^\mathbb{N}$ s.t. $\{f\mid f\circ f=g\}$ is not empty and finite?

$g(n)=n+2$ will do the trick.

Since this $g$ is injective, $f$ must be injective too, so under $f$ each natural number will have one successor and zero or one predecessor.

Also there are exactly two numbers that have no pre-predecessor, and that is only possible if there is exactly one number with no predecessor. There also can be no cycles in the action of $f$, because there are no cycles in the action of $g$. So the action of $f$ is fully specified by giving an enumeration of the natural numbers, and $f$ then just gives the successor of each of them.

The first two numbers in the enumeration must be the ones not hit by $g$, that is, $1$ and $2$. This makes the possible enumerations:

$$ 1,2,3,4,5,6,7,8,\ldots \quad \text{and}\quad 2,1,4,3,6,5,8,7\ldots $$ The first of these gives rise to $f(n)=n+1$, the other to $$ f(n) = \begin{cases} n-1 & \text{for even }n \\ n+3 & \text{for odd }n \end{cases}$$ and these are the only $f$ that produce $n\mapsto n+2$ when iterated twice.

Don't shoot me if I'm wrong, but I think this would be a huge hint:

Let $X$ be a set. It holds that $\lvert X\rvert \leq 1$ if and only if for every function $f : X \to X$, there is a function $g : X\to X$ with $f = g\circ g$.

The proof of this can be found in this link: Is every function $f : \mathbb N \to \mathbb N$ a composition $f = g\circ g$?