The accuracy of the many-body perturbation theory GW formalism to calculate electron-phonon coupling matrix elements has been recently demonstrated in the case of a few important systems. However, the related computational costs are high and thus represent strong limitations to its widespread application. In the present study, we explore two less demanding alternatives for the calculation of electron-phonon coupling matrix elements on the many-body perturbation theory level. Namely, we test the accuracy of the static Coulomb-hole plus screened-exchange (COHSEX) approximation and further of the constant screening approach, where variations of the screened Coulomb potential W upon small changes of the atomic positions along the vibrational eigenmodes are neglected. We find this latter approximation to be the most reliable, whereas the static COHSEX ansatz leads to substantial errors. Our conclusions are validated in a few paradigmatic cases: diamond, graphene and the C60 fullerene. These findings open the way for combining the present many-body perturbation approach with efficient linear-response theories.