Astrophysical black holes could be nearly extremal (that is, rotating nearly as fast as possible); therefore, nearly extremal black holes could be among the binaries that current and future gravitational-wave observatories will detect. Predicting the gravitational waves emitted by merging black holes requires numerical-relativity simulations, but these simulations are especially challenging when one or both holes have mass \(m\) and spin \(S\) exceeding the Bowen-York limit of \(S/m^2=0.93\). We present improved methods that enable us to simulate merging, nearly extremal black holes more robustly and more efficiently. We use these methods to simulate an unequal-mass, precessing binary black hole coalescence, where the larger black hole has \(S/m^2=0.99\). We also use these methods to simulate a non-precessing binary black hole coalescence, where both black holes have \(S/m^2=0.994\), nearly reaching the Novikov-Thorne upper bound for holes spun up by thin accretion disks. We demonstrate numerical convergence and estimate the numerical errors of the waveforms; we compare numerical waveforms from our simulations with post-Newtonian and effective-one-body waveforms; we compare the evolution of the black-hole masses and spins with analytic predictions; and we explore the effect of increasing spin magnitude on the orbital dynamics (the so-called "orbital hangup" effect).