The axioms of ZF set theory don't let you say "Just choose one at random from each of these uncountable many sets." To simply "choose one at random" you need an axiom to say that you are allowed to do that.
If it's only finitely many sets, finitely many choices, people are usually pretty happy with: "Well, choose one, then another, then another, and in a finite amount of time you'll be done, so that's OK."
If it's countably many sets then many people are happy saying: "Well, choose your first one in an hour, then the next one in 1/2 an hour, then the next in 1/4 of an hour, and so on, and after 2 hours you'll have made all your choices, so that's OK."
But with uncountably many sets neither of those works, and so you need an axiom to tell you that this is a permitted operation.
BTW, it's a separate issue, but in your first line, the part in parentheses does not imply, and is not an explanation of, the first part. These statements:
A: The reals are uncountably infinite;
B: There's an infinite number of real numbers between any two random real numbers.
These are largely unconnected. If you think otherwise then you might want to be a bit more careful and precise in your thinking. You might, of course, have simply mis-spoken yourself, in which case it's not a big deal.
(To start you off, the second statement is true of the rationals, and of the algebraics, both of which are countable).
I could understand the objection if one objected to the concept of infinity in the first place. Like "infinity is not real therefore any logical statement you make about it is non-sense".
What I don't understand is the mindset that would accept to be presented with an infinite number of sets but then not accept that you can choose an element from each set, because "the procedure will never be done" or something like that.
I can present you with a definition that specifies an infinite set. If you ask for an element, I can give you one. If you present me with a thing, I can tell you if it's in the set. In a very real sense it is completely specified.
Similarly defining an infinite collection of sets.
However, if I have an uncountable collection of non-empty sets, sometimes you can tell me how to choose one from each (for example, if I have uncountably many pairs of shoes then you can just say "pick the left one"), but within the axioms of set theory, if all you know is that there are infinitely many non-empty sets, the ZF axioms don't allow you to declare that there is a function which when given one of the sets, returns to you an element from that set.
Your statements seem to be saying "If you accept that there are infinite sets then you must accept that the Axiom of Choice is 'True'."
That turns out not to be the case. There are sets of axioms that result in systems that have infinite sets but in which the Axiom of Choice is not 'True'.
Another perspective on the Axiom of Choice would be to formulate it as “you can select one element from each set in a given set of sets, and the selected elements form a set”. So we accept the existence of infinite sets (since we have an axiom stating that infinite sets exist), but acknowledge that they are tricky and that not every “collection” of whatever constitutes a set. For example, a collection of all sets does not constitute a set. In this interpretation, you can still choose one element from a set of sets, but the Axiom of Choice tells you in addition that the result of such choosing is not just a collection of elements, but itself a set, so you can apply all other axioms and theorems of set theory to it.
If it's only finitely many sets, finitely many choices, people are usually pretty happy with: "Well, choose one, then another, then another, and in a finite amount of time you'll be done, so that's OK."
If it's countably many sets then many people are happy saying: "Well, choose your first one in an hour, then the next one in 1/2 an hour, then the next in 1/4 of an hour, and so on, and after 2 hours you'll have made all your choices, so that's OK."
But with uncountably many sets neither of those works, and so you need an axiom to tell you that this is a permitted operation.
BTW, it's a separate issue, but in your first line, the part in parentheses does not imply, and is not an explanation of, the first part. These statements:
These are largely unconnected. If you think otherwise then you might want to be a bit more careful and precise in your thinking. You might, of course, have simply mis-spoken yourself, in which case it's not a big deal.(To start you off, the second statement is true of the rationals, and of the algebraics, both of which are countable).