If photons have no mass, how can they have momentum?
There are two important concepts here that explain the influence of gravity on light (photons).
(In the equations below $p$ is momentum and $c$ is the speed of light, $299,792,458 \frac{m}{s}$.)
The theory of Special Relativity, proved in 1905 (or rather the 2nd paper of that year on the subject) gives an equation for the relativistic energy of a particle;
$$E^2 = (m_0 c^2)^2 + p^2 c^2$$
where $m_0$ is the rest mass of the particle (0 in the case of a photon). Hence this reduces to $E = pc$. Einstein also introduced the concept of relativistic mass (and the related mass-energy equivalence) in the same paper; we can then write
$$m c^2 = pc$$
where $m$ is the relativistic mass here, hence
$$m = p/c$$
In other words, a photon does have relativistic mass proportional to its momentum.
De Broglie's relation, an early result of quantum theory (specifically wave-particle duality), states that
$$\lambda = h / p$$
where $h$ is simply Planck's constant. This gives
$$p = h / \lambda$$
Hence combining the two results, we get
$$E / c^2 = m = \frac{p}{c} = \frac {h} {\lambda c}$$
again, paying attention to the fact that $m$ is relativistic mass.
And here we have it: photons have 'mass' inversely proportional to their wavelength! Then simply by Newton's theory of gravity, they have gravitational influence. (To dispel a potential source of confusion, Einstein specifically proved that relativistic mass is an extension/generalisation of Newtonian mass, so we should conceptually be able to treat the two the same.)
There are a few different ways of thinking about this phenomenon in any case, but I hope I've provided a fairly straightforward and apparent one. (One could go into general relativity for a full explanation, but I find this the best overview.)
The answer to this question is simple and requires only SR, not GR or quantum mechanics.
In units with $c=1$, we have $m^2=E^2-p^2$, where $m$ is the invariant mass, $E$ is the mass-energy, and $p$ is the momentum. In terms of logical foundations, there is a variety of ways to demonstrate this. One route starts with Einstein's 1905 paper "Does the inertia of a body depend upon its energy-content?" Another method is to start from the fact that a valid conservation law has to use a tensor, and show that the energy-momentum four-vector is the only tensor that goes over to Newtonian mechanics in the appropriate limit.
Once $m^2=E^2-p^2$ is established, it follows trivially that for a photon, with $m=0$, $E=|p|$, i.e., $p=E/c$ in units with $c \ne 1$.
A lot of the confusion on this topic seems to arise from people assuming that $p=m\gamma v$ should be the definition of momentum. It really isn't an appropriate definition of momentum, because in the case of $m=0$ and $v=c$, it gives an indeterminate form. The indeterminate form can, however, be evaluated as a limit in which $m$ approaches 0 and $E=m\gamma c^2$ is held fixed. The result is again $p=E/c$.
"momentum is the product of mass and velocity, so, by this definition, massless photons cannot have momentum"
This reasoning does not hold. Momentum is the product of energy and velocity.
"How is this momentum defined (equations)?"
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 (total energy dominated by rest-energy: $E = m c^2$, and therefore $p=mv$) as well as for massless particles like photons ($v = c$ and hence $p=E/c$).