Pulsars are some of the most accurate clocks found in nature, while black holes offer a unique arena for the study of quantum gravity. As such, pulsar-black hole (PSR-BH) binaries provide ideal astrophysical systems for detecting the effects of quantum gravity. With the success of aLIGO and the advent of instruments like the SKA and eLISA, the prospects for the discovery of such PSR-BH binaries are very promising. We argue that PSR-BH binaries can serve as ready-made testing grounds for proposed resolutions to the black hole information paradox. We propose using timing signals from a pulsar beam passing through the region near a black hole event horizon as a probe of quantum gravitational effects. In particular, we demonstrate that fluctuations of the geometry outside a black hole lead to an increase in the measured root mean square deviation of the arrival times of pulsar pulses traveling near the horizon. This allows for a clear observational test of the nonviolent nonlocality proposal for black hole information escape. For a series of pulses traversing the near-horizon region, this model predicts an rms in pulse arrival times of $\sim30\ \mu$s for a $3 M_\odot$ black hole, $\sim0.3\, $ms for a $30 M_\odot$ black hole, and $\sim40\, $s for Sgr A*. The current precision of pulse time-of-arrival measurements is sufficient to discern these rms fluctuations. This work is intended to motivate observational searches for PSR-BH systems as a means of testing models of quantum gravity.