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!
Cantor's diagonal argument proves (in any base, with some care) that any list of reals between $0$ and $1$ (or any other bounds, or no bounds at all) misses at least one real number. It does not mean that only one real is missing. In fact, any list of reals misses almost all reals. Cantor's argument is not meant to be a machine that produces reals not in your list. It's an argument by contradiction to show that the cardinality of the reals (or reals bounded between some two reals) is strictly larger than countable. It does so by exhibiting one real not in a purported list of all reals. The base does not matter. The number produced by cantor's argument depends on the order of the list, and the base chosen. In base $2$, you have no freedom in choosing the digits, so each ordering of the list produces in this way one real guaranteed not to be in the list. In other bases you have more freedom in choosing the digits, but this is irrelevant.
Best Answer
What you should realize is that each such function is also a sequence.
The diagonal arguments works as you assume an enumeration of elements and thereby create an element from the diagonal, different in every position and conclude that that element hasn't been in the enumeration.
To be concrete assume that $f_n$ is such an enumeration and consider the function
$$\phi(2n) = \begin{cases}b & \mbox{if } f_n(2n) = a\\ a & \mbox{otherwise}\end{cases}$$
Since $\phi(2n) \ne f_n(2n)$ we have that $\phi\ne f_n$.