It is not possible.
It is consistent with set theory without choice that $\mathbb R/\mathbb Q$ has strictly larger cardinality that $\mathbb R$. (This looks counter-intuitive, since $\mathbb R/\mathbb Q$ is a quotient.)
This is the case because, using a fact that goes back to Sierpiński (Sur une proposition qui entraîne l’existence des ensembles non mesurables, Fund. Math. 34, (1947), 157–162. MR0023318 (9,338i)), in any model of $\mathsf{ZF}$ where all sets of reals have the Baire property, it is not even possible to linearly order $\mathbb R/\mathbb Q$.
(Sierpiński argues in terms of Lebesgue measure. The argument in terms of the Baire property is analogous, and has the additional technical advantage of not requiring any discussion of consistency strength issues.)
A couple of years ago, Mike Oliver gave a nice talk on this topic (How to have more things by forgetting where you put them); he is not exactly using $\mathbb R/\mathbb Q$, but the arguments easily adapt. The point of the talk is precisely to give some intuition on why we expect the quotient to be "larger".
[Of course, in the presence of choice, the two sets have the same size. The argument above shows that the use of choice is unavoidable.]
When you say "we're not allowed to assume that the mapping from the naturals to the reals is a bijection to begin with", what you're referencing is the nature of the proof by contradiction; we did assume that the mapping was a bijection, and we derived a contradiction by producing a number that was missed by the map. Hence, we proved that no such bijection can possibly exist. In the strictest sense, you're "allowed" to assume a bijection between the naturals and the reals; you'll just find that you can derive a contradiction from that assumption via Cantor's diagonalization argument.
Similarly, you might try and take the same approach of assuming there is a bijection between the natural numbers and the rational numbers. You could try and apply Cantor's diagonalization argument to prove that it can't be surjective, but as your quoted answer explains, this doesn't work. Moreover, a bijection between the natural numbers and rational numbers can, in fact, be constructed. This means that, try as you might, if you do everything correctly, you'll never be able to derive a contradiction from this assumption.
Best Answer
The nicest trick in the book is to find a bijection between $\mathbb R$ and $\mathbb{N^N}$, in this case we are practically done. Why?
$$\mathbb{(N^N)^N\sim N^{N\times N}\sim N^N}$$
And the bijections above are easy to calculate (I will leave those to you, the first bijection is a simple Currying, and for the second you can use Cantor's pairing function).
So if we can find a nice bijection between the real numbers the infinite sequences of natural numbers we are about done. Now, we know that $\mathbb{N^N}$ can be identified with the real numbers, in fact continued fractions form a bijection between the irrationals and $\mathbb{N^N}$.
We first need to handle the rational numbers, but that much is not very difficult. Take an enumeration of the rationals (e.g. Calkin-Wilf tree) in $(0,1)$, suppose $q_i$ is the $i$-th rational in the enumeration; now we take a sequence of irrationals, e.g. $r_n = \frac1{\sqrt{n^2+1}}$, and we define the following function:
$$h(x)=\begin{cases} r_{2n} & \exists n: x=r_n\\ r_{2n+1} & \exists n: x=q_n \\ x &\text{otherwise}\end{cases}$$
Now we can finally describe a list of bijections which, when composed, give us a bijection between $\mathbb R$ and $\mathbb{R^N}$.