The gravitational waves emitted in the ringdown phase of binary black hole coalescence are a unique probe of strong gravity. At late times in the ringdown, these waves can be described by quasinormal modes, whose frequencies encode the mass and spin of the remnant, as well as the theory of gravity in play. Understanding precisely how deviations from general relativity affect the quasinormal mode frequencies of ringing black holes, however, is extremely challenging, as it requires solving highly coupled and sometimes higher-order partial differential equations. We here extend a novel approach, metric perturbations with spectral methods (METRICS), to study the gravitational metric perturbations and the quasinormal mode frequencies of ringing black holes in modified gravity. We first derive the asymptotic behavior of gravitational perturbations at the event horizon and spatial infinity for rotating black holes beyond general relativity. We then extend the eigenvalue-perturbation theory approach of METRICS to allow us to compute the leading-order beyond general relativity corrections to the quasinormal-mode frequencies and metric perturbations. As an example, we apply METRICS to black holes with moderate spins in scalarGauss-Bonnet gravity. Without decoupling or simplifying the linearized field equations in this theory, we compute the leading-order corrections to the quasinormal frequencies of the axial and polar perturbations of the nlm 1/4 022, 021, and 033 modes of black holes with dimensionless spin a <= 0.85. The numerical accuracy of the METRICS frequencies is <= 10(-5) when a <= 0.6, 10(-4) when 0.6 < a <= 0.7, and 10(-2) when 0.7 < a <= 0.85 for all modes studied. We fit the frequencies with a polynomial in spin, whose coefficients (up to second order in spin) are consistent with those obtained in previous slow-rotating approximations. These results are the first accurate computations of the gravitational quasinormal-mode frequencies of rapidly rotating black holes (of a similar to 0.85) in scalar-Gauss-Bonnet gravity.
