Yes, every function from $\mathbb Z^+$ to itself is indeed a countable set. However there are uncountably many of those.
Your mistake is that the set of functions (denoted by $\left(\mathbb Z^+\right)^{\mathbb Z^+}$) is not the union of all the functions. However you are correct that this union will be countable again.
Now, see that all the functions whose range is included in $\{1,2\}$ are also functions from the positive numbers to the positive numbers. It is a common exercise to show that this set corresponds to the power set of $\mathbb Z^+$. Cantor's theorem tells us that this power set is uncountable.
Also note that you are assuming the consequence. You assume that the set of functions is countable, so taking a union over this set will be a countable union, and therefore the set is countable. This is quite a circularity!
Here is an idea for how to use the diagonalization method after all.
Suppose $f_n$ is a list of surjections. We define $g$ in the following way:
$$g(k)=\begin{cases}\frac k2 & k\text{ is even}\\1+\sum_{m\leq k}f_m(k) &\text{otherwise}\end{cases}$$
So $g$ is clearly surjective (its restriction to the even numbers is surjective). To see that $g$ is not one of the $f_n$'s, we need to show that whenever $n\in\Bbb N$ there is some $k$ such that $f_n(k)\neq g(k)$.
Let $n\in\Bbb N$, and let $k$ be any odd number such that $n\leq k$, then we have that $$f_n(k)\leq\sum_{m\leq k}f_m(k)<1+\sum_{m\leq k}f_m(k)=g(k).$$
Therefore $f_n(k)\neq g(k)$ so $f_n\neq g$, and so we have that $g$ is not on the list.
If you are willing to use something other than diagonalization then we can give the following argument:
For every infinite subset of $\Bbb N$, we can write the following surjection:
$$f_A(n) =|\{a\in A\mid a<n\}|$$
Then $f_A$ is surjective because $A$ is infinite, so for every $n$ we can find $k$ such that $f_A(n)=k$.
Note that if $A\neq B$ then $f_A\neq f_B$: if $n=\min A\triangle B$, and suppose that $n\in A$, then $f_A(n+1)>f_B(n+1)$.
Therefore there are at least $2^{\aleph_0}$ surjections. Moreover all of them are non-decreasing!
Best Answer
Following a comment above: if one is allowed to use the fact that the set of all subsets of $\mathbb{N}$, $\mathcal{P}(\mathbb{N})$, is uncountable, then it is enough to observe that the set of functions from $\mathbb{N}$ to $\{0,1,2,3,4,5,6,7,8,9\}$ contains the set $\{0,1\}^{\mathbb{N}}$ of functions from $\mathbb{N}$ to $\{0,1\}$ (via an injection). And there is a clear bijection between $\mathcal{P}(\mathbb{N})$ and $\{0,1\}^{\mathbb{N}}$.