Yeah, overall palette offset would definitely be a useful/interesting tool, but more of a radical effect.
Another possibility would be allowing cycling between X number palettes on a per frame basis?
That way you could manually make X number of subtly different .ASE palettes and cycle them?
Perhaps this would be easier to implement?