Probability of picking an odd number from the set of naturals? I know there's no uniform distribution for a countably infinite set, but I'm wondering if there's still a way to determine the probability of picking from a subset of a countably infinite set.

For example, what's the probability that I pick an odd number from the set of naturals, assuming I'm picking randomly? Is this even a coherent question? If so, is there a textbook approach to this problem in measure theory/probability theory/probability measure?

Thanks!
I'd like to give a semi-philosophical, semi-mathematical defense of the answer 1/2.

The received view in contemporary mathematical probability theory, due to Kolmogorov, is that probability functions are normalized measures: nonnegative, countably additive set functions that are defined on $\sigma$-fields and that assign the sure event measure $1$. This hasn't always been the received view, however.

Bruno DeFinetti argued, famously, that the concept of probability does not mandate countable additivity. His argument is based on the fact, pointed out by you and commenters, that countable additivity rules out the possibility of a uniform distribution on the natural numbers. DeFinetti, a subjectivist, thought there was nothing rationally incoherent about distributing one's credences uniformly over $\mathbb{N}$, and, on these grounds, argued that the countable additivity axiom be weakened. For DeFinetti, probabilities need only be finitely additive.

Working in the tradition of finitely additive probability, it is indeed possible to define a uniform distribution on $\mathbb{N}$. The needed extension results can be found in Rao and Rao's Theory of Charges and Hrbacek and Jech's Introduction to Set Theory. I will sketch a construction here so that this answer has some mathematical content (if needed or requested, I will edit later to include more details).

First, we define the natural density, as in comments above, to be the limit (if it exists) $$ \lim_{n \to \infty} \frac{|A \cap \{1,...,n \}|}{n} = :d(A) $$ for $A \subseteq \mathbb{N}$.

It is not difficult to show

Proposition. (i) $d(\emptyset) = 0$ and $d(\mathbb{N})=1$. (ii) $d(\{n\})=0$ for all $n \in \mathbb{N}$. (iii) The set of numbers divisible by $m$ has natural density $1/m$. (NB: Some of this has been asserted in comments above, but I include it here for completeness.)

We then have the following theorem.

Theorem. There exists a finitely additive probability measure $P$ on $\mathscr{P}(\mathbb{N})$ that extends the natural density $d$.

Proof sketch. The proof relies on the existence of the Frechet ultrafilter $\mathcal{U}$ (the ultrafilter of cofinite sets) on $\mathbb{N}$, and is therefore non-constructive. We say a sequence $(x_{n})$ of real numbers is convergent in $\mathcal{U}$ with limit $x$ and write $x = \lim_{\mathcal{U}}x_{n}$ if for all $\epsilon &gt; 0$
$$\{n: |x_{n} - x| &lt; \epsilon  \} \in \mathcal{U}.$$
It can be shown that every real sequence has a unique $\mathcal{U}$-limit. It can also be shown that 
$$P(A) = \lim_{\mathcal{U}}\frac{|A \cap \{1,...,n \}|}{n}$$
is a finitely additive probability on $\mathscr{P}(\mathbb{N})$ extending $d$. $\square$

By the Theorem and the Proposition, $P$ is a finitely additive probability measure that assigns measure $1/2$ to the set of odd numbers.

Now, you may object that I've changed the subject by invoking merely finitely additive "probabilities". In response, I would remind you that the concept of probability predates the Kolmogorovian theory, and that there are good arguments (due to DeFinetti and other subjectivists) in favor of relaxing countable additivity in some contexts.
This is a great question that I as well don't know the answer to.

Also the probability cannot be 1. If the probability to choosing an odd number is 1, then the complement (the probability of choosing an even number is 0). However there are the same number of odd numbers and even numbers, therefore we can use the same proof to show that the probability choosing an even number is 1 leading to a contradiction. 

I'm guessing the other approach is first defining our measure. We can use the normalized counting measure (density) as our probability measure on $(\mathbb{N}, 2^\mathbb{N})$ we just need the set to be finite. This measure would imply that the probability is the same for each natural number.  

$$\mu(A) = \begin{cases}
|A| &amp; \text{if $A$ is finite} \\
\infty &amp; \text{if $A$ is infinite}
\end{cases}$$

The only problem that arises is that our set is infinite which will prevent us from having a our counting measure be a probability measure (we cannot divide by infinity). Maybe I'm mistaken, but it seems in order to solve this problem we can then cut up the natural numbers into a set of intervals, and prove it true for each interval. We then can extend it to projection maps.

We write the projection map as: $$\pi_k(\mathbb{N}) = \{k, k+1\} \text{ for any $k\in \mathbb{N}$ }$$ and define the new measure $\mu_k$ on $(\{k, k+1 \}, 2^{\{k, k+1\}})$ as $$\mu_k(A) =  \mu(A \cap \pi_k(\mathbb{N})) = \mathbb{P}(A)$$ for any $A \in 2^\mathbb{N}$. Now we solve what happens when we add union two spaces together to our probability. It seems that we must prove the probability is then the average the measures together, i.e., if we union the interval $\{k, k+1 \} \cup \{k+2, k+3\} = B$, then our measure would be $\mu(B) = \frac{\mu_k(B) + \mu_{k+2}(B)}{2}$ assuming we normalize each density in order for it to be a probability measure. 

Let $O = \{$ odd natural numbers$\}$. Then we can extend the measure to a limit after noticing $\mu_k(O) = \mu_{k+2}(O) = \dots = \mu_{k+2n}(O) = \frac12$ for any $n\in\mathbb{N}$. Our limit 
$$\mu(O) = \lim_{n\rightarrow\infty} \frac{\mu_1(O) + \mu_3(O) + \cdots + \mu_{1 + 2n}(O)}{n} $$
$$= \lim_{n\rightarrow\infty}\frac{\frac12 + \frac12 + \dots + \frac12}{n} = \lim_{n\rightarrow\infty} \frac{n\frac12}{n} = 1/2$$

Please correct me if you find any major errors.