Bijection from $\Bbb N\to \Bbb Z \times \{1, 2, 3, 4\}$.
Assuming $\mathbb{N} = \{0,1,2,3,...\}$, I will write two bijections.
Let $f: \mathbb{N} \rightarrow \mathbb{Z}$ be this function. $f(0) = 0$. $f(1) = 1$, $f(2) = -1$. $f(3) = 2$. $f(4) = -2$. Etc. This function is surjective because if I am given $z \in \mathbb{Z}$ is positive, we had $f(2z - 1) = z$. If I am given $z \in \mathbb{Z}$ is negative, we had $f(-2z) = z$. Also $f(0) = 0$. This function is injective because if $z_{1} = z_{2} \in \mathbb{Z}$, then under any of the three cases we are in ($2z-1$, $-2z$, or $0)$, these expressions coincide when we plug in $z_{1} = z_2$. Since the function is both surjective and injective, the function is bijective.
Let $g: \mathbb{Z} \rightarrow \mathbb{Z} \times \{1,2,3,4\}$ be this function. The Euclidean algorithm says $z = 4q + m$ where $q \in \mathbb{Z}$ and $m \in \{1,2,3,4\}$ and this choice of $(q,m)$ is unique once we have decided we take $m \in \{1,2,3,4\}$. The bijection is $g(z) = (q,m)$. This function is surjective because if I am given $(q,m)$, we had $g(4q+m) = (q,m)$. This function is injective because if I am given $q_1 = q_2 \in \mathbb{Z}$ and $m_{1} = m_{2} \in \{1,2,3,4\}$, then $4q_{1} + m_{1} = 4q_{2} + m_{2}$.
Both maps are bijective, so their composition is bijective.
The idea is to take a bijection from $\Bbb N$ to $\Bbb Z$ then "spread it evenly amongst the four equivalence classes modulo four". This can be done since the cardinality of $\Bbb N$ and $\Bbb Z^4$ is the same.
Define $\xi:\Bbb N\to \Bbb Z\times \{1,2,3,4\}$ by some ordinary map $\mu$ from $\Bbb N$ to $\Bbb Z$, like one from here and considering the input modulo four: $$\xi: n=4k+m\mapsto (\mu(k), [m]_4),$$ where $$[m]_4:=\{\ell\mid \ell=4h+m\text{ for some } h\in \Bbb N\}$$ and be sure to identify such an equivalence class with its representative in $\{1,2,3,4\}$, so $[0]_4$ is identified with $4$.
One could also argue for the existence of such a bijection alone by writing $$\Bbb Z\times \{1,2,3,4\}\cong \bigcup_{i=1}^4 \Bbb Z\times\{i\}$$ and saying that a countable union of countable sets is countable, hence a bijection with $\Bbb N$ exists.
Define $\sigma: \Bbb Z \times \{1, 2, 3, 4\} \to \Bbb Z \times \{1, 2, 3, 4\}$ by
$$ \sigma(z,k) = \left\{\begin{array}{lr} (z, k+1), & \text{for } z = 0 \, \land \, k \lt 4\\ (-1, 1), & \text{for } z = 0 \, \land \, k = 4\\ (z, k+1), & \text{for } |z| \gt 0 \, \land \, k \lt 4\\ (-z, 1), & \text{for } z \lt 0 \, \land \, k = 4\\ (-z-1, 1), & \text{for } z \gt 0 \, \land \, k = 4 \end{array}\right\} $$
Exercise: Show that $n \mapsto \sigma^n(0,1)$ is a bijective mapping between $\{0,1,2,3,...\}$ and $\Bbb Z \times \{1, 2, 3, 4\}$.