For $A=\mathbb{N}$ and $f:\mathbb{N} \to \mathbb{N}$ s.t $f(a)=a+1$ for all $a \in \mathbb{N}$, $f^n(a)$ will generate a strictly increasing sequence $\implies \forall n \geq 1, f^n(a)>a \implies \{a \in \mathbb{N} \mid \exists n \in \mathbb{N} \setminus\{0\} \text{ s.t } f^n(a)=a\}=\varnothing$.
From above counter-example, I think that the exercise may be not correct. Please correct if I'm wrong!
Thank you for your help!
For $f(a)=a+1$ we note that $f(\mathbb{N}+1) = \mathbb{N} +2 \subset \mathbb{N}+1$ and so $f$ will suit the criterion.
As for the hint being incorrect; first define $A_f$ to be the set in the question.
If $A_f \neq \emptyset$ then choose any $x \in A_f$ and define the finite set $B =\{f^n(x) :n \in \mathbb{N} \}$, then $B$ is non-empty and proper and $f(B)=B$.
If $A_f = \emptyset$ then we choose any $x \in A$ and define the set $C =\{f^{n+1}(x) :n \in \mathbb{N} \}$. If $x \in C$ then $x \in A_f$ so $x \notin C$ and $C \neq A$. Clearly $f(C)\subset C$ and so $C$ fits the requirements.
We finally note that for $A = \{0,1\}$ we have the counter-example given by $f(0)=1$, $f(1)=0$.