I know that the color rules are simple, but I want to make sure if I got it right. To my understanding we are allowed to use multiple color palettes, for example: red, blue, green, yellow     and    orange, cyan, black, white. As long as they are not visible at the same time on the screen 

Correct. As per the rules:
Color palettes must consist of a maximum of 4 colors. (Only 4 colors can be displayed on the screen at a time).
So you can have a different 4 color palette per stage if you wanted to.