A very simple low-tech solution:
Use one or more decks of cards
Shuffle the cards and lay face down.
Turn the top card for a random 50/50 decision: red or black.
Place in a discarded pile.
Shuffle and restart when they run out.
Two suggestions to make the last card unpredicatable:
Keep the Jokers in the pack and reshuffle when one is turned.
Cut the pack after each shuffle and put one part out of play.