As you said, the hack to get more than 256 colors is to redefine a sub rectangle with a new palette. But that's also the mechanism used to make animations. Are you able to get fluid playback with that?
Note: I'm not talking about new frame being just a new sub rectangle, more about N sub rectangles for the same frame, then a delay event, then M sub rectangles for the new frame, etc