Given two randomly chosen natural numbers, what is the probability that the second is greater than the first?

It is not possible to pick an integer in the range $[1,\infty)$ in such a way that each possible selection has equal probability, and you have discovered one of many arguments for this impossibility.

More specifically, assume that there was such a probability distribution. If the shared probability $p$ of choosing any particular number is greater than $0$, then it must also be greater than $\frac{1}{n}$ for some $n$ (that is how real numbers work). But then the total probability of getting one of the numbers $1$, $2$, $3,\ldots, n$ would be greater than $1$ which is absurd.

On the other hand, if $p=0$, then the probability of getting any natural number at all would be $0$ (which is also absurd). This is because probability distributions are required to be countably additive.

Therefore $p$ can neither be $0$ nor different form $0$, which is a contradiction; we must conclude that a probability distribution over the naturals where each outcome has equal probability is not possible.

As it was mentioned on an answer, you cannot find a way to uniformly choose a random natural number. One way to think about probabilities such as this is the concept of natural density. The natural density of a set $A \subset \mathbb{N}$ is defined as $\displaystyle\lim_{n \rightarrow \infty} \frac{|A \cap I_{n}|}{n}$ where $I_{n} = \{1, ..., n\}$. Thus for instance, the "probability that a randomly-picked number" is prime is the density of the set of primes (which is zero). If we interpret it this way, after you pick some number $k$, you want to find the density of $\{n \in \mathbb{N}; n \neq k\}$, and this is indeed 1. Notice that, however, this concept is not a probability measure. It doesn't satisfy the axiom of countable additivity; indeed, for each $k$, the set $\{k\}$ has density $0$ but $\displaystyle\bigcup_{k = 1}^{\infty} \{k\}$ has density $1$.