@rhettinger: the reason the ValueError gets raised correctly in the getrandbits-dependent branch is because getrandbits itself does a n<=0 check (in C for random.Random, in Python for random.SystemRandom).
So I thought the real reason why _randbelow does not perform the check was that it would be redundant, which it isn't when only random is used.

So instead of thinking about the suggested check as something that impacts performance (which certainly it does), I would rather see it as adding something into that second branch that was forgotten and gave that branch a performance benefit over the other one, which it never deserved.
It is also worthwhile to remember that any performance impact of this will only hit subclasses of random.Random that define random, but not getrandbits. Your alternative idea of having random.choice catch (ValueError, ZeroDivisionError) would affect random.Random and all subclasses.
If a subclass defines getrandbits, it needs to perform that check anyway  and, thinking about this more, I suggest that the requirement for any user-provided getrandbits to raise ValueError on k <= 0 should actually be added to the getrandbits docs.