It's an obvious and wellknown fact that there is no uniform probability measure on a set of natural numbers (i.e. the one that gives the same probability to each singleton). On a recent probability seminar one professor mentioned that this nonexistance is one of the main objections to measuretheoretic formulation of probability and that even Kolmogorov admitted the problem in it. What are possible solutions (i.e. alternative definitions of probability) to this problem? I'm looking either for an informative answer or a good reference.

The correct notion here is amenability. This means that there is a positive linear form $\phi$ on the space of bounded functions that is invariant under translations: $$\phi(\tau_nf)=\phi(f),\qquad\forall f\in\ell^\infty(\mathbb Z),n\in\mathbb Z,$$ where $\tau_nf(m):=f(m+n)$. As mentioned by Qiaochu, it is not countably additive, but only finitely additive (when applied to characteristic functions). It satisfies in addition $\phi({\bf 1})=1$. Of course, if $f$ has a finite support,then $\phi(f)=0$. Therefore, we must forget about "counting". Not every group is amenable. Free groups with two or more generators are not. Edit. As mentionned by Nate, one does not have an explicit form of $\phi$, because its existence follows from the axiom of choice. In particular, it is not unique. 


Some people object to countable additivity, and say that probability measures should be only finitely additive. There's a book called Theory of Charges (byI think?K. P. S. Bhaskara Rao) dealing with finitely additive measures and their theory of integration. I think Bruno de Finetti's book on probability theory may shed some light. 


One way to resolve your question is to ask what you would do next if you were able define a uniform distribution on the integers. What would you do with it? Maybe you could do just that, proceeding formally at first then justifying the procedure rigorously via a limiting process. In Bayesian statistics, you can often start with an "improper prior" distribution and end with a proper posterior distribution. That is, you can apply Bayes theorem starting with a "distribution" for your prior that isn't a probability distribution at all, such as a distribution that is 1 on all integers or all reals. And yet you can get a legitimate posterior probability distribution (depending on your likelihood function and possibly your observations). So at least in this context, you can proceed as if you had a uniform density on an unbounded set. Improper priors are analogous to generalized functions in analysis. You can rigorously define operators such as the delta "function" that are not functions at all. The theory starts by looking at what the desired behavior would be if such a function really existed and builds up a formalism (linear functionals on a space of test functions) that produces the desired behavior. 


I think the usual way is to define a sequence $f_n$ of probability measures whose limit has whichever property you consider to be the essence of uniformity (invariance under translation, the evens have probability 1/2, finite additivitiy, et cetera). For example, let $f_n(A) = A \cap \{1,2,\dots,n\}  / n$. Each $f_n$ is a probability measure, and the limit $\lim f_n(A)$ (if it exists) is called the natural density of $A$. Another example, let $f_n(A) = \zeta(1+1/n)^{1} \sum_{k\in A} k^{11/n}$. The limit $\lim f_n(A)$ (if it exists) is the logarithmic density of $A$. Another approach is to take an unlimited hyperinteger (as in, nonstandard analysis) $N$, and to take the measure $f(A)$ to be the standard part of ${}^\ast A\cap \{1,2,\dots,N\}/N$. This has a tendency to be meaningless, however, unless you can prove a result that works for all unlimited hyperintegers. Essentially, this is the same difficulty that arises in Denis Serre's answer. 

