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.

>>40
B-T doesn't work in dimension 1, though.

(Alright fine then, maybe I was wrong. :P )

Here are the papers anyway, just to prove it can be done, even if possibly not by that method:

Using Finitely Additive Probability: Uniform Distributions on the Natural Numbers
Joseph B. Kadane, Anthony O'Hagan; Journal of the American Statistical Association, Vol. 90, 1995

Uniform Distributions on the Natural Numbers
Oliver Schirokauer, Joseph B. Kadane; Journal of Theoretical Probability Volume 20, Number 3, September, 2007