Electron-phonon coupling and the emergence of superconductivity in intercalated graphite have been studied extensively. Yet, phonon-mediated superconductivity has never been observed in the 2D equivalent of these materials, doped monolayer graphene. Here we perform angle-resolved photoemission spectroscopy to try to find an electron donor for graphene that is capable of inducing strong electron-phonon coupling and superconductivity. We examine the electron donor species Cs, Rb, K, Na, Li, Ca and for each we determine the full electronic band structure, the Eliashberg function and the superconducting critical temperature Tc from the spectral function. An unexpected low-energy peak appears for all dopants with an energy and intensity that depend on the dopant atom. We show that this peak is the result of a dopant-related vibration. The low energy and high intensity of this peak are crucially important for achieving superconductivity, with Ca being the most promising candidate for realizing superconductivity in graphene.