Maybe this kata should be a [Code Golf] one?

Your parameters might be better expressed as booleans. While the idea of adding two booleans could be a little strange to new programmers, I think if you are emulating a purely boolean environment it makes sense to use them. (ie. one_bit_full_adder(True, False, True) => (True, False)). But that's just my opinion, feel free to disregard.

(It shouldn't even break existing solutions after all)

In this particular kata you don't need random tests, because you only have limited number of inputs. Instead, just test them all once. You may randomly shuffle the tests order, if you want.

Since you have a fixed number of outputs, I suggest changing output type to tuple.