Resonant inelastic X-ray scattering (RIXS) is used increasingly for characterizing low-energy collective excitations in materials. RIXS is a powerful probe, which often requires sophisticated theoretical descriptions to interpret the data. In particular, the need for accurate theories describing the influence of electron-phonon ($e$-p) coupling on RIXS spectra is becoming timely, as instrument resolution improves and this energy regime is rapidly becoming accessible. To date, only rather exploratory theoretical work has been carried out for such problems. We begin to bridge this gap by proposing a versatile variational approximation for calculating RIXS spectra in weakly doped materials, for a variety of models with diverse $e$-p couplings. Here, we illustrate some of its potential by studying the role of electron mobility, which is completely neglected in the widely used local approximation based on Lang-Firsov theory. Assuming that the electron-phonon coupling is of the simplest, Holstein type, we discuss the regimes where the local approximation fails, and demonstrate that its improper use may grossly textit{underestimate} the $e$-p coupling strength.