First, the axiom of choice requires that you have a countable number of sets that you are choosing elements from, but there are undoubtably many of the equivalence classes that he described [0]. So the author is using something stronger than the axiom of choice to arrive at his paradox.
Second, if you actually are in a situation where you have to choose from a countably infinite number of sets, you only need the axiom of choice if there is no selection rule for choosing an element available. In this case there is a rule you can use, namely: select the sequence in which the "finite prefix" is all zeros.
[0]: the number of equivalence classes is uncountable because there is a 1:1 relation between the equivelance class and an the infinite sequence that is common to all the sequences in the equivalence class once theirs uncommon prefixes have been truncated.