There are many ways to define an order on the rational numbers, which would establish a bijection to 0, 1, 2 ...

For instance, after reducing the numerator and denominator, so that you have unique rational numbers, you could define that they are ordered based on the sum of the number of digits of the numerator and of the denominator. This ensures that for each N that is the sum of digits, there are only a finite number of rational numbers. Inside this finite set, you can choose various rules, e.g. that positive numbers precede negative numbers, that a number with fewer digits in the denominator precedes another, etc. Then among the numbers with e.g. K digits in the numerator and L digits in the denominator, you could choose a lexicographic ordering, when the numerator is written before the denominator.

It does not matter which ordering rules you choose, the point is that you can always find such an order, which will arrange all rational numbers in a sequence, which describes thus a bijection with the natural numbers.

For algebraic numbers, you can establish such an order for the polynomials whose solutions they are, again finding a bijection. The easy solution is the same, to first establish an order between subsets of numbers that contain only a finite number of elements, and then define an order inside the subsets (e.g. with unique polynomials, where the coefficients do not have common factors, you can order them based on the sum of the number of digits of all coefficients).

The same technique works with any power of the set of rational numbers, or of the set of algebraic numbers.

For computable numbers, which are determined by programs written with an alphabet having a finite number of characters, you can define an order for the programs, e.g. first based on the length of the program, and then, among the finite number of programs having the same length, with lexicographic order.

With real numbers such methods do not work, because any attempt to arrange the real numbers into a sequence of subsets results in subsets that do not have a finite number of elements, like above, but which have an infinite number of elements.

The approach you mentioned would be if you used a non-bijective function to map from (N, N) to N like 2^a 3^b which can show that the cardinality of positive rationals is a subset of the cardinality of the naturals, and then you get your version of the proof.

Edit: Wait unless the objection was that actually the bijection from (N, N) -> N is not sufficient since e.g. (1,1) and (2,2) all map to the same rational. You could probably skip duplicates when enumerating, but if you insist on a explicit constructive version I have no idea how you'd find the inversion formula for that.