In condensed matter, it is often difficult to untangle the effects of competing interactions, and this is especially problematic for superconductors. Quantum simulators may help: here we show how exploiting the properties of highly excited Rydberg states of cold fermionic atoms in a bilayer lattice can simulate electron-phonon interactions in the presence of strong correlation - a scenario found in many unconventional superconductors. We discuss the core features of the simulator, and use numerics to compare with condensed matter analogues. Finally, we illustrate how to achieve a practical, tunable implementation of the simulation using painted spot potentials.