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.

This is a cute thread, and I like the Vitali set solution, but isn't this cheating?  The notion of "likelihood" just seems like an alternate phrasing of "probability" and if it is indeed supposed to be a different animal, then it hasn't been defined.

I don't feel we can speak about one choice being "more likely" than another in any definite way without resorting to some notion of measure.  The solution OP proposed seems to rely on saying that sets that are congruent modulo translation have the same measure - even though they are nonmeasurable!  For this to work we need to assert that a number randomly selected from the unit interval is as 'likely' to appear in one element in the partition as in any other - but again, this seems to resort to the idea of measure.

imo, this is a clever way of dodging the question rather than a solution to the question as asked.  I'd love for someone to convince me otherwise, though!