Proving that $\mathbb{N}\times \mathbb{N} \cong \mathbb{N}$ is incredibly useful for proving that the countable union of countable sets is countable and the fact that finite cartesian products of countable sets are countable.
Traditional proofs of this use Cantor's Pairing function, either using $(n,m)\mapsto 2^n3^m$ to give an injection (which is enough using Cantor-Schroeder-Bernstein Theorem or that an infinite subset of a countable set is countable; note I am by no means implying that either of these require any form of AC) or by giving an actual bijection via the map $(n,m)\mapsto \frac{(n+m)(n+m+1)}{2}+m$.
Another proof approach is to use the 'Countability Lemma' that given a function $f:X\rightarrow \omega$ such that every fiber $f^{-1}(n)$ is finite, then $X$ is countable. However, the proof (here) both implicitly uses the Axiom of Countable Choice and more arithmetic than I would like (to actually define the bijection outlined). I should point out that the choice used in the proof is that it chooses for each natural number $n$ a bijection from $n$ to $f^{-1}(n)$.
What I am looking for is a proof that $\mathbb{N}\times \mathbb{N}\cong \mathbb{N}$ without the use of either $AC_\omega$ or any arithmetic.
Arithmetic that is as simple as the addition of two natural numbers is okay, since it can be easily shown to correspond to $n+m := \left| n\coprod m \right|$. A less trivial example of something that is 'okay' is the fact that there are a finite number of pairs $(n,m)$ that add up to a given number. However, have as little arithmetic as possible is a plus; some examples of things that are too much include factoring or any mention of the rationals or reals (e.g. no floor or ceiling function). The point is base the bijection only on the properties of $\omega$ as the minimal inductive set and the properties that follow immediately from this.
$AC_\omega$ is certainly not required to show that $\mathbb{N}\times \mathbb{N}\cong \mathbb{N}$ is true, nor should arithmetic on $\mathbb{N}$ be necessary to define such a bijection (though clearly it simplifies things).
As a final note, I am using 'countable' to mean in bijection with $\omega$.
We can define a sequence $A_n$ of subsets of $\omega $ ($=\mathbb{N}$) by recursion. $A_0 = \{ 2n : n \in \omega\}$ and similarly $A_{i+1}$ is "every other" element of $\omega \setminus A_i$. To be more direct, we define that $n \in A_j$ if and only if there is a sequence of functions $(f_0, \ldots, f_j)$ from $\omega$ to $\omega$ such that $n$ is in the range of $f_j$, $f_0$ enumerates "every other" element of $\omega$, and for all $k < j$, $f_{k+1}$ enumerates "every other" element of $\omega \setminus \operatorname{range}f_k$.
Here we say that a function $f$ enumerates "every other" element of an infinite $X \subseteq \omega$ if $f$ is increasing, $f(0) = \min X$ and, for all $i$, there is exactly one element of $X$ between $f(i)$ and $f(i+1)$. Notice that arithmetic whatsoever is required in that definition; it is purely order theoretic.
Now we can prove, again without any arithmetic, that $\omega$ is the disjoint union of $\langle A_i : i \in \omega\rangle$. In particular, each $k$ is either in $A_k$ or in $A_j$ for some $j < k$.
Thus there is a function $f$ such that $f(n) = (i,j)$ exactly when $n$ is the $j$th element of $A_i$. This is the desired bijection between $\omega$ and $\omega \times \omega$.