We develop an approximation-free diagrammatic Monte Carlo technique to study fermionic particles interacting with each other simultaneously through both an attractive Coulomb potential and bosonic excitations of the underlying medium. Exemplarily we apply the method to the long-standing exciton-polaron problem and present numerically exact results for the wave function, ground-state energy, binding energy and effective mass of this quasiparticle. Focusing on the electron-hole pair bound-state formation, we discuss various limiting cases of a generic exciton-polaron model. The frequently used instantaneous approximation to the retarded interaction due to the exchange of phonons is found to be of very limited applicability.