We run into essentially the same problem almost any time we try to combine the real numbers as described by mathematics with probability theory.
When applying probability theory to something like a coin flip, a die, or a deck of cards, we use what's known as a Probability Mass Function to assign a probability value to each possible result. What's the probability rolling this fair six-sided die will give 3? 1/6.
But as you noticed, this type of probability model doesn't work well when trying to work with real numbers, because there are just too many of them. Since there are more real numbers even within a min-to-max interval than there are natural numbers, if you try to assign a single non-negative probability to each number in the domain and require they add up to 1, almost all of them will need to be zero.
So instead, when dealing with a domain of real numbers, probability theory normally switches to using a Probability Density Function. This function assigns a real value to every possible outcome in the domain, but these values are not probabilities. Instead, to get a probability from a probability density function, you need to take the integral of the function from a start point to an end point, and this represents the probability the result will be between those points.
For a simple example, a process that generates a random real number
x chosen out of the interval from 0 to 1 such that the likelihood is the same over the entire interval could be represented by the function
p(x)=1. The probability of "
x is between 0 and 1/4" is the integral from 0 to 1/4 of 1, which is 1/4. The probability of "
x is exactly 1/4", if meaningful at all, would need to be the integral from 1/4 to 1/4 of 1, which is 0. So even though the probability of any particular exact value is zero, you still have a probability of 1 that the value is somewhere in the interval, and meaningful probabilities for any smaller pieces of the interval you care to calculate.
Real numbers tend to be useful in physics because generally speaking you can divide ordinary quantities of distance, time, mass, and energy into arbitrary intervals (and sometimes non-algebraic numbers like pi and e pop up in the useful models). Of course as modern science ran into observations now attributed to atoms and photons, and developed the Standard Model of particle physics, we needed new theories that no longer assume mass and energy are indivisible on the smallest (non-ordinary) scales. Could the same happen for distance and time? Who knows?
By the way, probability density functions turned out to be rather useful in physics too: basic quantum mechanics describes position and momentum of an object in the form of complex-valued "wave functions" which obey Schrödinger's Equation. The squares of the absolute values of these wave functions are actually probability density functions for the variable being described. These wave functions do still assume real-valued position, time, and momentum.
Finally, some of the promising looking ideas about quantum gravity (including string theory) suggest there may in fact be a minimum or fundamental unit of space-time, somewhere around the scale of the Planck Length. But as far as I've heard, none of these are quite on the level of an established useful theory yet.
Now, all this goes to show that there are ways around the paradox, and ways to still describe our observed universe fairly well using both real numbers and probability. But that doesn't necessarily imply that's the true fundamental nature of the universe, or anything like that. It's also possible to construct working physical laws using just rational numbers, or numbers which are all multiples of some single chosen very small number. (But those systems may not be as easy to calculate with!) All any physical theory or law can claim is that it does well at explaining and predicting observations, and possibly covers more observations than other theories, and/or is simpler and easier to understand and use than other theories.
So when it comes to questions like: Does the universe truly work this way or that? or Does a "better" set of physical theories get us closer to understanding a true underlying nature of the universe? or Why can we predict that things will happen at all? ... we're into the interesting realm of metaphysics. But that's another story (and one I'm not so qualified to comment on).