But what does "picking at random" mean? If you think it's obvious that you can just make infinitely many random choices at the same time, you're endorsing the axiom of choice.

(If you think you can make one random choice at a time, you're endorsing the axiom of finite choice, which is just true. Determinism doesn't matter here, but "at the same time" matters a lot.)