I think the answer is no, because being an natural number object is a universal property and being a model of Nelson arithmetic is not.

As long as a category is Heyting (is a regular category where the inverse image maps between subobject lattices have right adjoints) it is possible to talk about models of any first order theory inside the category. There is a problem though: often the models of a first order theory are not unique up to (unique) isomorphism in Heyting categories. So being the model of a first order theory in a Heyting category isn't often a universal property.

A natural number object is *not* essentially a model of Peano arithmetic, as Peano arithmetic has many non standard models. I would say that it is essentially a model of second order arithmetic, although this doesn't directly make sense in other categories than toposes.

Nelson arithmetic is weaker than Peano arithmetic, and therefore has the same non standard models, if not many more. One could say that there are usually are many non isomorphic Nelson natural number objects. But I don't think this is what you mean.

After Francois' comment, I might have a better idea of what you are looking for. I suppose you want something like a natural number object, that happens to force Nelson's arithmetic in the internal language.

The definition of natural number object makes sense in arbitrary monoidal categories, if formulated properly. In these contexts we still have all primitive recursive functions, though; they don't have the restrictions in complexity that the survey article on Nelson's arithmetic mentions. So removing structure from the ambient category is insufficient.

*Linear logics* are capable of controlling complexity, and I would look for an answer there. The idea is that the ambient category has an endofunctor $!$, and that recursion does not give you morphisms from the natural number object $N$, but from $!N$ instead. You can now control the debt of recursion in functions $N\to N$ by controlling which morphisms $!N\to N$ factor though a canonical morphism $!N\to N$. I have tried to find a related universal property a couple of months back, but have been unsuccessful.

notbe cartesian closed, so no λ-calculus. $\endgroup$ – David Roberts Jan 27 '13 at 3:01