The King's Chalice

A king has captured 100 prisoners, but he's bored and wants to entertain himself. He's going to give the prisoners a chance to be released, so he poses the following challenge:

The king will call prisoners, one by one, into a meeting room. In the meeting room, there's a table with a chalice on it. Each prisoner has the choice to flip the chalice upside down, or, if it's already upside down, flip it right-side up. The king will not interfere with the chalice between prisoners. They don't have to flip the chalice if they don't want to. The king will use a random number generator to determine which prisoner will be called into the room, and he will continue to call prisoners in forever.

If the prisoners can announce to the king that they have each been called into the room at least once, then they will all be released. However, if they're wrong, they will all be executed.

The king gives the prisoners one night to discuss a strategy beforehand. What should they do?

Source: The green book