Let $\mathcal{E}$ be an elementary topos.
Call an object $X\in \mathcal{E}$ Dedekind-infinite when it admits a monic but not epi endomorphism.
I wonder if in an elementary topos the existence of a Dedekind-infinite object is equivalent to the existence of a Natural Numbers Object.
I remark that I do not know if any of this is true. So I am also interested in counterexamples.
Below is an attempt of proof for $"\Rightarrow"$ which probably does not work as noted in the comments.
Call a sub-object $S \subset X$ $t$-stable when $s\in S \Rightarrow ts \in S,$ and define the orbit $O(x)$ of an element $x$ as the interesection of all $t$-stable sub-objects containing it (this definition makes sense in any elementary topos).
We have $O(x)=\{x,tx,ttx,\cdots\},$ i.e. contains $x$ and nothing else than what can be obtained by applying $t$ finitely many times to $x.$
Now suppose that $X\in \mathcal{E}$ is Dedekind-infinite, and call $t:X\to X$ the monic non-epi endomorphism; then it must exists an element $x:1\to X$ which is not in the image of $t$ (again, all this can be said in an elementary topos).
Then in this case the elements in the orbit are all different since if it were $t^n(x)=t^m(x)$ for some $m<n$ we would have $t(t^{n-1})(x)=t(t^{m-1})(x)$ and thus since $t$ is monic we could iterate backwards to obtain $t^{n-m}(x)=x$ contrary to the fact that $x$ does not belong to the image of $t.$
Since the very definition of orbit already encodes recursion provided the elements in the orbit are all different, we have that $O(x)$ satisfies the universal property of NNO.
Provided that the above is correct, I have problems with the reverse implication $"\Leftarrow".$
I tried showing that an NNO must be Dedekind-infinite but failed. Maybe one should show that if $N$ is an NNO, then $X=\mathcal{P}(N)$ is Dedekind-infinite? (If that were the case I would also like to see an example of an NNO which was not Dedekind-infinite).
The forward direction is false. Consider a product $\mathcal{E}=\mathcal{C}\times \mathcal{D}$ where $\mathcal{C}$ is a topos with a Dedekind-infinite object $X$ (e.g., the category of sets) and $\mathcal{D}$ is a topos without an NNO (e.g., the category of finite sets). Then the object $(X,Y)$ is Dedekind-infinite for any object $Y$ of $\mathcal{D}$, but $\mathcal{E}$ has no NNO, since both Dedekind-finiteness and being an NNO can be tested on each factor separately.
One place your argument goes wrong when it asserts the existence of $x:1\to X$ which is not in the image of $t$: $t$ could be surjective on global elements, but not epic. For instance, if $Y$ has no global elements, then $(X,Y)$ will have no global elements either so a non-epic monic $t:(X,Y)\to (X,Y)$ will trivially be surjective on global elements.
More fundamentally, even if such an $x$ does exist, you seem to be tacitly assuming that your object $O(x)$ is a coproduct of countably many copies of the terminal object, one for each $t^nx$. (If this is not what you have in mind then I have no idea how you are proposing to use "recursion" to verify the universal property of an NNO.) But this need not be true. For instance, in my example above where $\mathcal{C}$ is the category of sets and $\mathcal{D}$ is the category of finite sets, the object $(\mathbb{N},\{*\})$ has a monic non-epic endomorphism whose image is missing a global element $(0,*)$ but the stable subobject it generates is not a coproduct of copies of $1$ (it is on the first coordinate but not the second).
The reverse direction is also false: consider the trivial (one-object) topos, which has a NNO but no Dedekind-infinite object. In a nontrivial topos, though, an NNO is always Dedekind-infinite. Indeed, if $N$ is an NNO then the zero map $1\to N$ and successor map $s:N\to N$ make $N$ a coproduct of $1$ and $N$. It follows that $s$ is monic, and $s$ is only epic if $1$ has at most one map to every object. Considering maps to exponential objects, this means there is at most one map between any pair of objects, and then considering the subobject classifier every object has only one subobject. In particular the subobject $0\to X$ is an isomorphism for all $X$ so every object is initial and the category is trivial.