The coin flip method you describe breaks the same-query same-server locality (unless adding or removing servers) that is one motivation for the consistent hashing method.
You could solve that by storing the new-query flip result, but the goal was reducing storage…
I'm assuming all coin flips are deterministic based on the task. In this case, it'd be equivalent to generating a slightly longer hash and using a couple of bits for the "coin flip". (Or just generating a new hash with 1 or 3 bits or whatever you need.)
You could solve that by storing the new-query flip result, but the goal was reducing storage…