Your error is in the assertion:
... we will end up with a sequence of non-zero digits, which forms a valid Natural number...
Natural numbers have only finitely many nonzero digits in their decimal expansion. This can be proven by induction: it is true of $1$; and the number of nonzero digits in the decimal expansion of $n+1$ is at most one more than that of $n$ (you need at most one more digit before you start padding with $0$s on the left).
An infinite list which contains infinitely many nonzero digits does not yield a natural number. In fact, one can prove that your procedure will produce a sequence of digits with infinitely many nonzero digits, hence not correspond to a natural number.
Let's say that your procedure selects $0$ whenever possible (that is, whenever the $i$th digit, from right to left, of the $i$th natural number, is nonzero; you really want this, because if you insist, as in your post, that you always select a nonzero digit, then you guarantee what you get is not a natural number). Can the list be arranged in such a way that the $i$th digit of the $i$th number is nonzero for all $i\gt N$ for some $N$? No: for any given $N$, there are $10^{N-1}$ natural numbers that require fewer than $N$ digits to write; since there are only $N$ positions prior to $N$, at least one of these $10^{N-1}$ numbers must be listed in a position below $N$; but if it is listed in position $j\gt N$, then its $j$th digit will be $0$, so the constructed sequence will necessarily have a nonzero entry at $j\gt N$. Since this holds for all $N$, the list obtained is never eventually $0$, and so does not correspond to a natural number.
Now, if you want to extend your notion of numbers to include expressions with infinitely many nonzero digits, then your argument is correct: the set of all such "numbers" is not countable. However, those are not the natural numbers.
It is indeed $2^{\aleph_0}$. $\Bbb N$ has $2^{\aleph_0}$ subsets altogether, so certainly it has no more than $2^{\aleph_0}$ infinite subsets. On the other hand, there is an injection $\varphi$ from $\wp(\Bbb N)$ into the set of infinite subsets of $\Bbb N$.
Let $O=\{2n+1:n\in\Bbb N\}$, the set of odd positive integers. Then for each set $S\subseteq\Bbb N$ let $$\varphi(S)=O\cup\{2n:n\in S\}\;.$$
Since $\varphi(S)\supseteq O$ for every $S\subseteq\Bbb N$, every $\varphi(S)$ is infinite. On the other hand, it’s clear that $\varphi$ is injective (one-to-one), since whenever $S_0,S_1\subseteq\Bbb N$ with $S_0\ne S_1$, $\varphi(S_0)\setminus O\ne\varphi(S_1)\setminus O$, and therefore $\varphi(S_0)\ne\varphi(S_1)$.
Intuitively, $\varphi(S)\setminus O$ looks just like $S$, except that it’s been blown up by a factor of $2$: it’s simply the double of $S$. Thus $S$ is completely recoverable from the even numbers in $\varphi(S)$: just divide each of them by $2$. This ensures that $\varphi$ is an injection. Throwing in $O$ just ensures that $\varphi(S)$ is always infinite.
Thus, if $\mathscr{A}$ is the set of infinite subsets of $\Bbb N$, $\varphi$ is an injection of $\wp(\Bbb N)$ into $\mathscr{A}$, while the identity map is an injection of $\mathscr{A}$ into $\wp(\Bbb N)$, and it follows from the Cantor-Schröder-Bernstein theorem that $|\mathscr{A}|=|\wp(\Bbb N)|=2^{\aleph_0}$.
Best Answer
If $\sigma=\langle n_k:k\in\Bbb N\rangle$ is monotonically non-decreasing, let $\hat\sigma=\langle n_{k+1}-n_k:k\in\Bbb N\rangle$; then $\hat\sigma$ is an arbitrary sequence in $\Bbb N$. (My $\Bbb N$ includes $0$.) (If you meant $\sigma$ to be strictly increasing, replace $n_{k+1}-n_k$ by $n_{k+1}-n_k-1$.) The map $\sigma\mapsto\hat\sigma$ is a bijection between the set of monotonically non-decreasing sequences in $\Bbb N$ and the set of all sequences in $\Bbb N$. If you know that the latter set is uncountable, you’re done. If not, observe that it contains the set of sequences of zeroes and ones, which are just the indicator (or characteristic) functions of subsets of $\Bbb N$, so there are uncountably many of them.