Binary pulsars allow us to carry out precision tests of gravity and have placed stringent bounds on a broad class of theories beyond general relativity. Current and future radio telescopes, such as FAST, SKA, and MeerKAT, may find a new astrophysical system, a pulsar orbiting around a black hole, which will provide us a new source for probing gravity. In this paper, we systematically study the prospects of testing general relativity with such black hole-pulsar binaries. We begin by finding a mapping between generic non-Einsteinian parameters in the orbital decay rate and theoretical constants in various modified theories of gravity and then summarize this mapping with a ready-to-use list. Theories we study here include scalar-tensor theories, varying $G$ theories, massive gravity theories, generic screening gravity and quadratic curvature-corrected theories. We next use simulated measurement accuracy of the orbital decay rate with FAST/SKA to derive projected upper bounds on the generic non-Einsteinian parameters. We find that such bounds from black hole-pulsars can be stronger than those from neutron star-pulsar and neutron star-white dwarf binaries by a few orders of magnitude when the correction enters at negative post-Newtonian orders. By mapping such bounds on generic parameters to those on various modified theories of gravity, we find that one can constrain the time variation in Newton's constant $G$ to be comparable and complementary to the current strongest bound from solar system experiments. We also study how well one can probe quadratic gravity from black hole quadrupole moment measurements of black hole-pulsars. We find that bounds on the parity-violating sector of quadratic gravity can be stronger than current bounds by six orders of magnitude. These results suggest that a new discovery of black hole-pulsars in the future will provide powerful ways to probe gravity further.

12 figures, 18 pages, fixed 2 minor typos