Does the following provide an "intuitive demonstration" of Tennenbaum's theorem ?
A countable Non Standard Model of PA has its domain of the form ($\mathbb{N}$, Z-Chain). As the domain is countable and of a simple form there is a recursive mapping "R" from $\mathbb{N}$ to ($\mathbb{N}$, Z-Chain). As an example, a domain ($\mathbb{N}$ , Z) can be recursively mapped from $\mathbb{N}$ by assigning even numbers to $\mathbb{N}$ and odd numbers to Z. As a result this domain is known to PA and it is possible to undertake a form of recursive PA on this domain ($\mathbb{N}$, Z-Chain) using e.g. $\oplus$ = fn1(+,x,R), $\otimes$ = fn2(+,x,R) with fn1, fn2 both recursive. So the intriguing question is why can't a countable model of PA : ($\mathbb{N}$,$\boxplus$,$\boxtimes$,0,1) with recursive $\boxplus$ and $\boxtimes$ be used to represent a countable Non Standard Model of PA : (($\mathbb{N}$, Z-Chain), +, x,0,1), since there is a recursive map from $\mathbb{N}$ to ($\mathbb{N}$, Z-Chain)?
A Non Standard Model is created by appending to PA a formula defining a non-standard element via a constant "c". So to represent the new knowledge about c in a model of PA : ($\mathbb{N}$,$\boxplus$,$\boxtimes$,0,1) requires a new form of 'plus' $\boxplus$ = fn3($\oplus$,c), and/or a new form of 'times' $\boxtimes$ =fn4($\otimes$,c). This is because the attempt to model a Non Standard Model of PA using the usual axioms of PA don't include information about the constant c, so the information about c needs to be wrapped up in at least one of $\boxplus$ or $\boxtimes$. So the recursiveness or not of $\boxplus$, $\boxtimes$ will depend upon the complexity of the defining formula for c.
The constant c represents an infinite object in the Non Standard Model, which is equivalent to postulating an axiom of infinity, which is at least a $\sum ^0_2 $ formula and cant be simpler (e.g. $\exists$x $\forall$y (0 $\in$ x AND ((y$\in$x) -> (S(y) $\in$ x))) using set theory). So since $\boxplus$ = fn3($\oplus$,c) and/or $\boxtimes$ = fn4($\otimes$,c) becomes non-recursive, there is no countable model of PA : ($\mathbb{N}$,$\boxplus$,$\boxtimes$,0,1) with recursive $\boxplus$, $\boxtimes$ that can be used to represent a Non Standard Model (($\mathbb{N}$, Z-Chain), +, x,0,1) of PA. The countable domain ($\mathbb{N}$, Z-Chain) of the Non Standard Model can still be recursively defined, via the recursive map from $\mathbb{N}$, but all the subsets of the domain cant be, due to the required presence of the information relating to the infinite object c.
A minor comment: note that your description of countable nonstandard models of PA is incorrect: the underlying ordering is $\mathbb{N}+\mathbb{Q}\cdot\mathbb{Z}$, that is an initial segment that looks like the standard natural numbers followed by densely many $\mathbb{Z}$-chains. This isn't a real issue though, since this order still has lots of computable presentations.
More importantly, you seem to conflate an infinite element in the sense of nonstandard models with the axiom of infinity in set theory, and this is unjustified. Also, there is no reason for any nonstandard element $c$ to be definable: in fact, if $\mathcal{M}$ is a nonstandard elementary extension of $\mathbb{N}$, then the definable elements of $\mathcal{M}$ are exactly the standard ones.
So what is going on in Tennenbaum's theorem?
The issue in Tennenbaum's Theorem isn't the complexity of a formula defining an infinite element; rather, it is the coding power that such elements provide. Any natural number codes a sequence of natural numbers via its expansion into prime factors, e.g. $90$ codes the sequence $\langle 1, 2, 1\rangle$ since $90=2^13^25^1$. Note that this sequence involves more than just the multiplicative structure - we have to have an ordering of the primes (otherwise we'd just get a multiset). Now a nonstandard element of a model $\mathcal{M}$ may code a nonstandard-length sequence of possibly-nonstandard elements.
In particular, a nonstandard number may also code a nonstandard-length sequence each of whose standard terms is a standard natural number; e.g. the number $\prod_{i<b}p_i^b$ codes the sequence $\langle 1, 2, 3, 4, ..., b-2, b-1, b\rangle$, and if we take $b$ to be nonstandard this sequence's "standard part" is $\langle 1, 2, 3, ...\rangle$. This leads to the notion of the standard system of a model: $SS(\mathcal{M})$ is the set of $A=\{a_0<a_1<...\}\subseteq\mathbb{N}$ such that for some $b\in\mathcal{M}$, the sequence $b$ codes begins with $\langle a_0, a_1, a_2, ...\rangle$.
The key observation is this:
This is because from $b$ we can effectively read off the $n$th term of the sequence coded by $b$, for $n$ standard, as long as each standard term of that sequence is a standard natural number. As a consequence, if the standard system of $\mathcal{M}$ contains even one noncomputable set, then $\mathcal{M}$ is not computable. Tennenbaum's theorem is proved then by showing that every nonstandard model has a standard system which codes at least one (in fact, many) noncomputable set.
The proof that the standard system contains lots of noncomputable sets uses a neat trick. Let $T$ be a computable infinite binary tree with no computable infinite paths (this is a standard exercise in computability theory). Since $T$ is computable, it is definable in the language of arithmetic, so has a "nonstandard version" $T^*$ in $\mathcal{M}$; moreover, it can be defined by a "nice" formula, in that $T^*$ extends $T$.
By overspill, there is some node $c\in T^*$ of nonstandard height (otherwise since $T$ is infinite and $T\subseteq T^*$ the set of heights of nodes of $T$ would define the standard natural numbers inside $\mathcal{M}$). Now take the sequence of $0$s and $1$s describing the (nonstandard length) path leading up to $c$; this can be coded by a nonstandard natural number in $\mathcal{M}$ (actually according to most ways of defining binary trees inside arithmetic, $c$ itself is actually a code for this path, but whatever), and since $c$ has nonstandard height and $T\subseteq T^*$ the standard part of this sequence is an infinite (hence noncomputable) path through $T$ which is in the standard system of $\mathcal{M}$.