Ab initio calculations of the phonon-induced band structure renormalization are currently based on the perturbative Allen-Heine theory and its many-body generalizations. These approaches are unsuitable to describe materials where electrons form localized polarons. Here, we develop a self-consistent, many-body Green's function theory of band structure renormalization that incorporates localization and self-trapping. We show that the present approach reduces to the Allen-Heine theory in the weak-coupling limit, and to total energy calculations of self-trapped polarons in the strong-coupling limit. To demonstrate this methodology, we reproduce the path-integral results of Feynman and diagrammatic Monte Carlo calculations for the Fröhlich model at all couplings, and we calculate the zero point renormalization of the band gap of an ionic insulator including polaronic effects.