You don't need the axiom of choice for the following statement:
If $X$ is countable, and $f$ is a function whose domain is $X$, then the range of $f$ is countable.
You also don't need the axiom of choice for the following statement:
$\Bbb{N\times Z}$ is countable.
Finally, define $f(n,m)=\frac nm$ or $0$ if $m=0$, and show that this is a surjection onto the rational numbers.
The simple short answer is that infinity is weird and does not fit well with intuition which was developed in the real world of finite things.
An early challenge to intuition is whether or not there is a single infinity. Is the set of integers greater than or equal to zero bigger than the set of integers strictly greater than zero because it has one more element? Is the set of all integers twice as big because it has the negatives as well?
We can only start to answer this after we have defined what we mean for two, possibly infinite sets, to have the same size. The most common definition is that two sets have are the same size if a bijection (one-to-one and onto map) can be found between them. We quickly run into another challenge. With familiar finite sets, if we find a map which is one-to-one but not onto then we would deduce that one is smaller than the other. So, this suggests that the examples which I just gave are different sizes. However, we find that the existence of a one-to-one but not onto map does not preclude a bijection. A bijection can be found between all of those sets so they are the same size. We find that further intuitively bigger sets are also the same size e.g. the rational numbers and the algebraic numbers. The algebraic numbers are those which are the roots of polynomials with integer (or rational) coefficients. They include some irrationals, e.g. $\sqrt 2$ but not others, e.g. $\pi$.
We usually say "cardinality" rather than "size" which mainly emphasizes that we are using this interpretation. I will stick to "size" as we are talking about intuition.
We might start to develop the intuition that all infinite sets are the same size but now we find that the real numbers are strictly bigger. A bijection between the natural numbers and the real numbers is not possible.
How much bigger? Is it the next biggest set or is there something with an intermediate size? Now it gets really weird. Not only do we not know but we can prove that we cannot prove that there is or is not a set with an intermediate size. Look up the Continuum Hypothesis if you want to know more.
We know that the reals are not the biggest set. For any set, we can construct a bigger one so there is no biggest one.
Now back to some of your points. It is indeed counter-intuitive that all of these are true at once:
- Between any rationals there is an irrational
- Between any irrationals there is a rational
- There are more irrationals than rationals
1 and 2 suggest that they alternate along the real line and hence there are equally many but 3 contradicts this. Along with the Continuum Hypothesis, I think that you just have to work on understanding the proofs and then learn to accept it. I still find it weird but not as weird as the Continuum Hypothesis.
The problem with Hallström cuts is that you don't have the irrationals until you have the reals. The irrationals are just the reals which are not rational. So, you would have to obtain the irrationals somehow else before you could start work on Hallström cuts. We know how to construct the rationals without the reals so we can use them as a starting point. You could perform cuts on the algebraic numbers and that would work because we could construct them without the reals. However, you would just get something isomorphic to the usual reals.
It is often said, without good evidence, that contemplating infinity drove Cantor mad. Even if not true, the existence of the story shows that struggling to understand infinity is common.
Best Answer
In the proof of uncountably many irrational numbers, you just need to show it is real and not in the list already. However for rational numbers, you also need the decimal expansion to be periodic, which cannot be ensured by diagonization, even when you're constructing $x$ from rational numbers with only $1$ and $0$.
An example would be the Liouville Number which only has $1$ and $0$, but is not periodic and thus not rational.