How to pythonically select a random index from a 2D list such that the corresponding element matches a value?

I have a 2D list of booleans. I want to select a random index from the the list where the value is False. For example, given the following list:

[[True, False, False],
 [True, True, True],
 [False, True, True]]

The valid choices would be: [0, 1], [0, 2], and [2, 0].

I could keep a list of valid indices and then use random.choice to select from it, but it seems unpythonic to keep a variable and update it every time the underlying list changes for only this one purpose.

Bonus points if your answer runs quickly.