Your problem is not that the algorithm changes at some threshold. Your problem is instead that the number of random bits extracted from the RNG is non-uniform and dependent on both RNG state and parameters.
This also holds for the sampling algorithm beyond the threshold.
It is indeed hard to avoid that issue: If you consume at most k bits from the random stream, then all probabilities are integer multiples of 2^-k.
And random bits are cheap – none of the sampling algorithms are especially stingy in their random consumption.
The appropriate generic way is to fork the RNG state, call whatever sampling algorithm with the forked RNG, and then discard the fork.