$E = mc^2$ is the rest energy, that is, the energy associated with its intrinsic mass. Photons have no rest energy as they have no mass, but that doesn't mean they don't have energy. All their energy is kinetic energy. So you cannot use just $E = mc^2$ here. The full equation that includes all energy, both the rest energy and kinetic energy, is
$$E^2 = m^2 c^4 + p^2 c^2$$
Note the quadratic: this is not a simple sum of energies. (What it really is is better seen if one takes it in Planck units: then it is $E^2 = m^2 + p^2$ which can be rearranged to $m^2 = E^2 - p^2$ which says the mass is the length of the space-time momentum of the particle. Photons have no space-time momentum. In this case their temporal momentum, which is their energy, must equal their spatial momentum. There is no excess energy, i.e. no rest mass. It's a really beautiful aspect of the geometry of Einstein's relativity, itself a wonderful thing to behold. It is just soo cool!) The first part is essentially the rest energy, the second part is essentially the kinetic energy (not entirely literally, due to the quadratic). If you take a photon, $m = 0$ but we still have $p^2 c^2$ left, and you take the square root of that puppydog and you get
$$E = pc$$
Now you can set that to $h\nu$
$$h\nu = pc$$
so
$$\nu = \frac{pc}{h}$$
If there's any momentum at all, and there must be for the photon to exist, there will be a nonzero frequency.
FWIW you can write down an equation that has a straight sum of rest energy ($E = mc^2$) and kinetic energy by a relativistic kinetic energy equation too that is analogous to Newton ($K =\frac{1}{2}mv^2$), but the latter becomes undefined for mass 0, since it is written in terms of velocity, and all photons have the same velocity ($c$). (Mathematically it gives the nonsense expression $0 \cdot \infty$.) So you need to use this as it works in all situations. The trick with photons is their kinetic energy is thus seen to be not dependent on velocity or mass, but momentum, and passing to the quantum theory, on frequency, or wavelength.