Can you pick a random natural number? And a random real number?

The question is what does it mean "by random". Remember that mathematics is built on precision. This means that the terms you are using has to have a precise meaning (or at least a reasonably obvious way how to translate them to such).

Random is not one of these terms. The natural meaning of "random" really just means "arbitrary". To choose an arbitrary element from a non-empty set you don't need anything except existential instantiation, which allows us to go from "There is something" to "This is something". Of course you can't say which element was taken when you instantiate an existential quantifier. That's the true sense of the word arbitrary.

On the other hand, from the probability point of view, random just means that you have some distributions which tells you what are the odds of an element being chosen from a particular collection of element. It might not be able to assign probability to every possible collection, though.

Probability has a few axioms, one of them says that given countably many pairwise disjoint sets, the probability of being in one of them is the sum of all probabilities. Another is that the probability of picking out any element is $1$.

Now it's easy to see why a countably infinite set does not have any probability which assigns singletons probability $0$. Because a countably infinite set can be written as the countable union of singleton, and the axioms of probability would mean that we assign the probability of picking any element from the set as $0$, which is impossible. On the other hand, you can't have that the probability for any number is equal to the other, and non-zero, since then the probability for picking just anything is infinite (it will be the sum of a constant positive number). So essentially it says that some numbers will have a better chance being chosen than others, which might not fit with the natural meaning of the word "random", which we like to think about as a uniform distribution, allowing each possibility the same chance of being selected.

On the real numbers it's better, though, as an uncountable set, and more specifically a set which has those lovely features that the real numbers enjoy from. These allow us to define an assortment of probabilities where singletons have probability $0$. We can restrict ourselves to the interval $[0,1]$, and not the entire set of real numbers, and then we have a very nice probability, which assigns an interval $[a,b]$ the probability of its length, $b-a$.

So far, we have no made any appeal to the axiom of choice. Or have we? It turns out that without the axiom of choice it is possible that the real numbers could be expressed as the countable union of countable sets. If we allow a probability to be countably additive, this means that there is no way to define a probability on the real numbers. We simply extend the problem from countable sets to the real numbers. Note that this doesn't mean that the real numbers are countable, the fact that the countable union of countable sets is countable depends on the axiom of choice.

But finally, you might notice, we haven't picked any number! This is because probability doesn't really deal with picking the actual number, just with the odds of the number being in one set or another. The closest to picking a number that I can think of, an arbitrary number, is existential instantiation that we talked about earlier.

There are distributions over all natural numbers, such as the Geometric distribution, and distributions over all real numbers, such as the normal distribution.

But there is no uniform distribution in either case. You can see this as follows: if there were a uniform distribution over natural numbers, it would have to assign some probability $p$ to each natural number. If $p = 0$ then the total probability $\sum_{n\in\mathbb{N}} p(n)$ is 0. But if $p > 0$ then the total probability is $\infty$. In either case we don't have a valid distribution.

Similarly, if there were a uniform distribution over real numbers, it would have to assign some probability $p$ to each interval of the form $[n, n+1)$ for $n\in\mathbb{Z}$. Then an equivalent argument to the above shows that $p$ can't be 0 nor greater than 0 so no such distribution exists.

If you mean something else, please clarify your question.

The first question is easier: to decide what it means to pick a random natural number, we need a probability distribution, which is just an assignment of a probability $p_n$ to each $n$ such that $\sum p_n=1$. But to have that sum, we can't have all $p_n$ equal-so in that sense there's no standard way to pick a random natural number.

In the case of the natural numbers, it's easy enough to describe how to make a choice once we've chosen a distribution: assign to each $n$ the interval $I_n=[\sum_{m< n} p_m,\sum_{m \leq n} p_n]\subset [0,1]$, then flip a bunch of coins to get an approximation of some real number $x\in [0,1]$ (specifically, a segment of the binary expansion of $x$.) After enough flips we'll learn in which $I_n$ $x$ lies, and then choose $n$ as our "random" number. Observe this definitely does not appeal to the axiom of choice: AC is really about choosing elements of abstract sets, whereas it's very easy to choose elements of $\mathbb{N}$ since the natural numbers have so much structure.

Things get trickier in the case of the real numbers. For the same reason as above, there's no distribution with equal probabilities for all numbers, but it's worse: there actually can't be more than countably many numbers with a nonzero probability at all! (This follows from the fact that an uncountable sum of positive numbers is always infinite.) In fact the most interesting probability distributions on real numbers assign a probability of zero to every real. In that case there's really no way to pick a random real, because the intervals corresponding to $I_n$ above are only a single point, and we can't pick out a single real number by flipping a finite number of coins. But we do have positive probabilities of landing in certain intervals $[a,b]$. Making those intervals very small and picking randomly from them-according to some probability distribution-is the closest one can get to picking a random real number.