Let's say an isolated atom emits a photon. The excited state in the atom has some lifetime $\tau$. Through the energy-time uncertainty relation, that gives the excited state some uncertainty in energy $\delta E\sim h/\tau$ (not the same as $\Delta E$, which is a difference in energy between atomic states). The photon then has the same uncertainty $\delta E$ in its energy, which corresponds to an uncertainty in frequency. The photon isn't in an eigenstate of energy.
For many real-life examples such as a visible photon emitted by a hydrogen atom, or gamma-rays emitted by beta-decay daughters, $\tau$ is very long compared to $h/\Delta E$, so we have $\delta E \ll \Delta E$. The uncertainty $\delta E$ is also often very small compared to the limitations imposed by, e.g., Doppler shifts or the resolution of the detector.
Yes, when you measure the energy of the photon, you get a random outcome. However, there is a quantum-mechanical correlation between this energy and the energy of the atom, so that energy is exactly conserved (not just statistically, on an average basis).