Here's a reasonably direct way that doesn't require developing arithmetic or limits in $\mathbb R$, or even arithmetic on $\mathbb Q$, if only we know that $\mathbb Q$ is densely ordered in the sense that for any $a<b$ there exists at least one $c$ with $a<c<b$.
First, since we already know that $\mathbb Q$ is countable, fix a bijection $\psi:\mathbb N\to\mathbb Q$. (I'm assuming $0\notin\mathbb N$, for notational convenience).
Lemma. Let $f$ be any function $\mathbb N\to\mathcal P(\mathbb Q)$. Then there exists an $A\in\mathbb R$ such that $A$ is not in the range of $f$.
Proof. Set $a_0 = 0$, $b_0 = 1$, and define a sequence of pairs of rational numbers $(a_n,b_n)$ by doing the following for $n=1,2,3,\ldots$:
- Let $I_n = \{q\in\mathbb Q \mid a_{n-1} < q < b_{n-1}\}$ and $B_n = f(n) \cap I_n$.
- If $B_n$ is nonempty, then let $a_n=a_{n-1}$ and $b_n = \psi(\min\psi^{-1}(B_n))$ -- that is the first rational number in $B_n$, according to the enumeration $\psi$.
- Otherwise, let $a_n = \psi(\min\psi^{-1}(I_n))$ and $b_n=b_{n-1}$.
We see that $a_0 \le a_1 \le a_2 \le \cdots$ and $\cdots \le b_2 \le b_1 \le b_0$, and that $a_n<b_n$ for every $n$. Now let
$$ A = \{ q\in \mathbb Q \mid \exists n: q<a_n \} $$
It is easy to verify that $A$ is a Dedekind cut. Furthermore, every $f(n)$ is different from $A$. Namely: if $B_n$ was nonempty, then $f(n)$ contains $b_n$, but $A$ doesn't. Otherwise, $A$ contains a number between $a_{n-1}$ and $a_n$, but $f(n)$ doesn't.
End proof.
Now, to see that there are uncountably many irrationals, let $g:\mathbb N\to\mathbb R$ be any countable sequence of (Dedekind representations of) irrational numbers. We must then find an irrational number that is not in the range of $g$.
Consider the function
$$ f(n) = \begin{cases} g(n/2) & \text{when $n$ is even} \\
\text{the Dedekind cut for }\psi(\frac{n+1}{2}) & \text{when $n$ is odd} \end{cases} $$
The range of $f$ is the range of $g$ together with all of the rational numbers. So when the Lemma gives us an $A$ that is not in the range of $f$, then this $A$ is (1) irrational, and (2) not in the range of $f$, as required.
