Like all paradoxes, there is no contradiction here, just misuse of logic.
How do you define velocity? If you say
the distance traveled in an extended period of time, divided by that time
well then of course there's no such thing as instantaneous velocity. Asking what something's instantaneous velocity is under this definition is logically equivalent to something like
Let $n$ be the number of apples in a nonempty container of apples. What is $n$ when the container has no apples?
The question doesn't make sense, and simply cannot be answered.
Now one can often extend definitions so that terms get defined in new circumstances, consistent with the cases for which they were previously defined. We define velocity as
$$ v = \lim_{\Delta t \to 0} \frac{\Delta x}{\Delta t}. $$
This is consistent with the old in the sense that if you have a constant velocity $v$ and you travel for an extended period of time, $v$ is given by distance divided by time.
But make no mistake, our new definition goes beyond cases of extended time intervals, and in these cases the old definition still fails, just as it always did. Sure no motion occurs if no time elapses. So what? If no time elapses, the definition of velocity has nothing to do with actual distance traveled over that time.
Some object may have a nonzero velocity because our new definition of velocity says it does, whereas the old definition may have had nothing to say one way or the other. Make no mistake, the old definition does not say the velocity of an object is $0$ if no time elapses. It says the velocity of an object is currently undefined if no time elapses.
Best Answer
Zeno used his paradoxes to proof movement was impossible. But of course he knew movement existed! If you were going to punch him, he will not trust your fist would have to get infinite times half of the way before reaching him; he would try to avoid it. His philosophical motivation was to "stirr" the reason, show that by logical arguments we can fall into wrong conclusions, ergo incurring in fallacies. This was a big thing, because in the age of the reason, someone shown that logic may take us nowhere.
I imagine it was the equivalent in modern times to Heisenberg Principle in Quantum Mechanics, where in the age where science was believed to be infinitely precise, it was shown that there were unmeasurable things in Physics (the flagship of science!); or Gödel's theorem, where he shown that there are things in Mathematics that cannot be proven right or wrong.
From a conceptual point of view, instantaneous velocity is a limit: if you compute the average velocity ($\Delta x / \Delta t$) for every smaller values of $\Delta t$, you will see that it nicely converges to a value: this is the instantaneous velocity.
From an experimental point of view, this is unreachable. You cannot measure arbitrarily small periods of time just because your equipment has a limit. Also, your measurement of the position has a precision too. Error analysis will show you that, assuming the velocity is constant along an interval, and for noisy measurements of $x$ and $t$, the bigger the step, the more accurate the measurement will be. For a real movement, where the velocity is not constant, expanding the interval will increase the error introduced by variability. If you have an idea of the evolution of the velocity (for example, the second derivative computed from the last few points), one could estimate the optimal interval for maximum precision.
From a theoretical physics point of view, things get weirder. You cannot trully define the position, or the momentum, with infinite precision. And if you go to very small scales, and very short times, you will hit the weirdness of Plank foam: where time and space are predicted to not behave in any intuitive way.