Can a Skip card be played before all the players have had at least one chance to play? Or can it be played at anytime?
There is no such restriction. From the rules:
The player ends the turn by discarding one card of choice onto the discard pile.
SKIP CARDS: When discarded, a "Skip " card causes another player to lose their next turn. The player who discards the "Skip " card chooses the player who loses their turn. When a player draws a "Skip " card, the player may discard it immediately or save it for a later turn. A "Skip " card may never be used in making Phase 8, or any other Phase. A "Skip " card may never be picked up from the discard pile.