I finally cleaned up my benchmark script, which feels like a big hack.  I should really learn to use pyperf or something.

Inspired by your comment about 3.8 on the Mac I tried my Ubuntu installation's stock 3.8.  I get a small degradation (~0.5%) for powers of two and 4-5% speedups just below powers of two and for shuffle.  (This is under the slightly strange situation where _randbelow is using the main branch code but everything else in the class is imported from 3.8.)

_randbelow_without_getrandbits() is consistently (if only slightly) faster, as you would expect for cases that are basically guaranteed to call self.random() only once.

I am impressed (if not necessarily surprised) by the variation between builds, especially with my friend's ARM builds which reached nearly 20% for one case.  So I completely understand if it's less uncertain just to pass.  Thanks for your attention, in any event!