"momentum is the product of mass and velocity, so, by this definition, massless photons cannot have momentum"
This is where your reasoning goes astray. Momentum is the product of energy and velocity. Inserting factors of $c$, the relativistically correct relation between momentum $p$ and velocity $v$ is $c^2 p = E v$. This holds for non-relativistic massive particles ($E = m c^2$) as well as for massless particles like photons ($v = c$).