Wally says "you can use this card on your first turn or on a Pokemon that was put into play this turn". Does that mean I can use Wally on the very first turn of the game when I am not allowed to play Supporter cards?

No, Wally does not override the game rule of the player going first not being able to play Supporter cards on their first turn. You can only play Wally on your first turn if you are going second.

Relevant cards