How can there be really any instantaneous velocity? I have read about Zeno's arrow paradox that tells us there is no motion of the arrow at a particular instant of its flight. It can be inferred that there can be no velocity at any instant. Moreover we cannot calculate velocity at any instant in the real world (of course it can be done by using calculus) but how can this be possible? What is the intuition behind this concept?
 A: At a "frozen" instant of time, the arrow may not be moving - but this is a tautology, since movement is something that requires time. However, even in that frozen instant the arrow does have a velocity (instantaneous velocity, if you will). Imagine that time is a series of huge number of discrete frames (or instead imagine that it is continuous, and that we are taking finer and finer discrete approximations). The position of the arrow jumps to the right from frame to frame. How does the arrow "know" how far to travel from one frame to the next? If the only piece of information "stored" in one frame were its position, then the arrow wouldn't be able to determine this! The necessary information, which is the instantaneous velocity of the arrow, must be as much a part of this frozen frame as all the information related to the arrow's position.
More formally, one says that the configuration space of a physical system, which is the set of all information needed to predict its future (and thus all the information associated with a point in time) includes not only the list of positions of all objects, but also their velocities.
A: bright magus puts his finger on the problem when he says in a comment: There is no movement without time flow.
Physicists describe the universe as a four dimensional manifold, in which points are identified by their position $(t, x, y, z)$. The time coordinate $t$ is just a coordinate like $x$, $y$ and $z$, and there is no sense in which time is flowing. We are used to differentiating with respect to time e.g. velocity = $dx/dt$, but there is nothing special about time. For example if you have every seen a road sign warning you about a steep hill, the gradient on the sign is $dz/dx$. As far as I know Zeno never complained that you can't have hills because you can't calculate $dz/dx$, and he should not have made the corresponding complaint about $dx/dt$.
At this point you're going to object that everyone knows time flows. After all we can sit at constant spatial coordinates just by staying still, but there is no way to stay at a constant time coordinate. True, but the perception of time flowing is likely an artefact of human consciousness rather than a fundamental principle of physics.
If you search this site for flow of time you'll find several questions exploring exactly this issue.
A: I'd like to add something to these answers. In the classical mechanics, we cannot distinguish a moving body from the body at rest, if we look at it at any particular instant. So, we have to add some hidden information to the picture, that is instantaneous velocity. But that's what physics only knew in the 19th century. In 20th century physics, there have several more deep and precise pictures appeared.
First, special relativity. It tells that the moving body contracts by the Lorentz factor. So if we know the size of the body at rest, we can calculate its speed, and in 3D - the line of motion. Only the direction of motion remains unknown, but motion and rest are clearly distinct.
Second, the theory of field, for example electrodynamics (in fact, it arose in the end of 19th century). It tells that a charged particle is accompanied with electric and magnetic fields, and they show the velocity of the particle, $\vec{B}=\tfrac{1}{c}\vec{v}\times\vec{E}$ in Gaussian units. Electrically neutral bodies consist of many charged particles (electrons and nuclei), and their microscopical fields contain the same information.
And at last, quantum mechanics. It tells that any particle is represented at any instant by its wave function. And the wave function is not only the probability distribution - it does have phase, and its phase shows the motion. Namely, there is the velocity operator which is $\hat{\vec{v}}=-\tfrac{i\hbar}{m}\nabla$, and applying this operator to the wave function, one can get expectation value of velocity and some more detailed information. For example, if the wave function at some instant is $\Psi=\Psi_0\exp(ikx)$, then the probability density is flat for any $k$, but $\hat{\vec{v}}\Psi=\tfrac{k\hbar}{m}\vec{\imath}\Psi$ shows that the particle has velocity $k\hbar/m$ along the $x$ axis.
I think Zeno would be happy to know these theories.
A: 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. 
