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.

Any solution using the Axiom of Choice fails OPs condition. He said "Create a method to...", not "Show that a method exists to...". Since none of the proofs shown using the Axiom of Choice show how to find the element they says exists, the method as a whole fails to show how to find a random natural number.