Structural phase transitions and soft phonon modes pose a long-standing challenge to computing electron-phonon (e-ph) interactions in strongly anharmonic crystals. Here we develop a first-principles approach to compute e-ph scattering and charge transport in materials with anharmonic lattice dynamics. Our approach employs renormalized phonons to compute the temperature-dependent e-ph coupling for all phonon modes, including the soft modes associated with ferroelectricity and phase transitions. We show that the electron mobility in cubic SrTiO_{3} is controlled by scattering with longitudinal optical phonons at room temperature and with ferroelectric soft phonons below 200 K. Our calculations can accurately predict the temperature dependence of the electron mobility in SrTiO_{3} between 150-300 K, and reveal the microscopic origin of its roughly T^{-3} trend. Our approach enables first-principles calculations of e-ph interactions and charge transport in broad classes of crystals with phase transitions and strongly anharmonic phonons.