For example, you could use something like this and due to the way you UV wrap, the 8x8 texture rule would not be broken. You could have one 8x8 texture per colour, or 64 colours per 8x8 texture, or somewhere in between.
