The root of the problem is that you think of momentum as being defined to be the product of something's mass and its velocity, but this is actually only an approximation that just so happens to work extremely well at our everyday scales; the actual definition of momentum is the spatial frequency of the wave function (which is like a special kind of distribution). Thus, because photons can have a spatial frequency, it follows simply that they therefore can have momentum.

Something else that likely contributes to your confusion is that you probably think that where something is and how fast it is going are two completely independent things, but again this is actually only an approximation; in actuality there is only one thing, the wave function, which is essentially overloaded to contain information both about position and momentum. Because you cannot pack two independent pieces of information into a single degree of freedom, it is not possible for position and momentum to be perfectly well defined at the same time, which is where the Heisenberg uncertainty principle comes from.