We introduce massive black holes (BHs) in the Feedback In Realistic Environments (FIRE) project and perform high-resolution cosmological hydrodynamic simulations of quasar-mass haloes [Mhalo(z = 2) ≈ 1012.5M⊙] down to z = 1. These simulations model stellar feedback by supernovae, stellar winds and radiation, and BH growth using a gravitational torque-based prescription tied to the resolved properties of galactic nuclei.We do not include BH feedback. We show that early BH growth occurs through short (≲1Myr) accretion episodes that can reach or even exceed the Eddington rate. In this regime, BH growth is limited by bursty stellar feedback continuously evacuating gas from galactic nuclei, and BHs remain undermassive in low-mass galaxies relative to the local MBH-Mbulgerelation. BH growth is more efficient at later times, when the nuclear stellar potential retains a significant gas reservoir, star formation becomes less bursty and galaxies settle into a more ordered state. BHs rapidly converge on to the observed scaling relations when the host reaches Mbulge ~1010M⊙. We show that resolving the effects of stellar feedback on the gas supply in the inner ~100 pc of galaxies is necessary to accurately capture the growth of central BHs. Our simulations imply that bursty stellar feedback has important implications for BH-galaxy relations, AGN demographics and time variability, the formation of early quasars and massive BH mergers.