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.

>>15
By using the standard construction of unmeasurable sets as in the wikipedia article (or, better yet, this version: http://everything2.com/title/unmeasurable%2520set), you can partition the unit interval I=[0,1] into a countable union of disjoint subsets, each of which is identical to all the others, only translated left or right by some real number, so that they're all the same size (even though they don't really have a "size", strictly speaking, since they're unmeasurable).  Number these sets V_1, V_2, ....

Now just select a random number x \in [0,1] (which can be done with the coinflip thing, since an infinite number of non-zero digits *after* the decimal point is OK), and let your random integer be the index i of the set V_i that x happens to be in.

Since you can't have a probability space that contains all the V_i, you can't talk about the "probability" of choosing 7567865 (or whatever), but since the chance of choosing 7567865 only depends on the size and shape of V_{7567865}, which is the same as all the other V_i's, no number is more likely to be chosen than any other.