You should be able to solve this.

Create a method to choose a random integer between 0 and infinity such that no integer is more likely to be chosen than any other.

Yes it is possible, I don't care what your probability book says (Notice I didn't even use the word "probability").  You may assume the axiom of choice.

How's that any better than the flipping the coin thing?  We imagine that all infinity digits are chosen at once anyhow, not simply from left to right as though we were reading them.