We use a Luttinger-Ward functional approach to study the problem of phonon-mediated superconductivity in electron systems with strong electron-electron interactions (EEIs). Our derivation does not rely on an expansion in skeleton diagrams for the EEI and the resulting theory is therefore nonperturbative in the strength of the latter. We show that one of the building blocks of the theory is the irreducible six-leg vertex related to EEIs. Diagrammatically, this implies five contributions (one of the Fock and four of the Hartree type) to the electronic self-energy, which, to the best of our knowledge, have never been discussed in the literature. Our approach is applicable to (and in fact designed to tackle superconductivity in) strongly correlated electron systems described by generic lattice models, as long as the glue for electron pairing is provided by phonons.