Berarducci and Otero in "A Recursive Nonstandard Model of Normal Open Induction" (Journal of Symbolic Logic v61, 1966) give a discretely ordered ring $R$ with recursive operations having the following properties:
- $R$ is integrally closed in its quotient field. (So elements with "rational" square roots are perfect squares.)
- The prime elements of $R$ are cofinal
- $R$ satisfies the induction axioms for quantifier-free formulas
In an earlier paper of Otero (Journal of Symbolic Logic, vol 55, 1990) Otero proves that every model of Open Induction extends to one in which Lagrange's Four-Square Theorem holds. Whether this can be done effectively I don't know.
As for the general question "What properties can a recursively presented discretely ordered ring share with $\mathbb{Z}$": Let's say that a discretely ordered ring $R$ is "diophantine correct" if it satisfies all universal sentences that hold in $\mathbb{Z}$. Assuming that the language of rings has signature $(+, -, \times , \le,0 ,1)$, diophantine correctness amounts to the requirement that any system of polynomial equations and inequalities that are solvable in $R$ is solvable in the standard integers. Incidentally, models of open induction satisfy a weaker property: Any system of equations solvable in some (at least one) model of open induction has a p-adic solution.
The question whether a nonstandard diophantine correct model of open induction can be effectively constructed was raised by Adamowic and Morales-Luna in "A Recursive Model for Arithmetic with Weak Induction", (Journal of Symbolic Logic v50, 1985). I believe that this question is still open. I also believe that the models constructed in the Otero-Berarducci paper are in fact diophantine correct, but the proof of this seems to bump up against open problems in number theory. This is all discussed in an article on diophantine correct open induction by Sidney Raffer in "Set theory, Arithmetic, Philosophy: Essays in Memory of Stanley Tennenbaum (edited by J. Kennedy and R. Kossak), Cambridge University Press. (To appear.)