Tic Tac Toe Game - Player Indicator
You could use a TFF(Toggle Flip Flop).



From wikipedia: https://en.wikipedia.org/wiki/Flip-flop_(electronics)


  If the T input is high, the T flip-flop changes state ("toggles") whenever the clock input is strobed. If the T input is low, the flip-flop holds the previous value.


This is how i would implement, there may be better implementations. 

The TFF gonna hold the information about players turn, if you connect "player A LED" to Q and "player B LED" to Qnot, one will always be the oposite of the other, so only one is on at time, which tells you which player turn is. Then to change between turns, you should toggle the flip flop. To achieve this you should hold the T input HIGH and make a single pulse in the clock input, that will invert the logic state of Q and Qnot, making each "player turn LED" switch its state. 

To achieve the random player turn generator, you can hold the T input HIGH, while the game is off, and put a clock signal in the clock input. The higher the clock frequency the better randomness you'll get, but be aware of your circuit limitations. That will make your Q and Qnot switch fast when the game if off. When the "begin game button" is pressed, the clock signal should stop pulsing, stoping in a "quite random" logic state, indicating which player turn it is. I say quite random cause it is quite difficulty, if not impossible, to achive real randomness in eletronics, but if you use a high frequency clock it should be pretty hard to control, through a mechanical switch, which player turn it will output.  

If you still have some dificulty implementing this i suggest you doing some reaserch on T-Flip Flop, im sure there is a lot in the internet about. Also trying to implement a discrete TFF on a simulator should make it easier to understand it.