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$ (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 an eigenstate of energy.
For many real-life examples such as a visible photon emitted by a hydrogen atom, $\tau$ is very short, so we have $\delta E \ll \Delta E$.
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).