Actually, doing some numbers in my head, it might technically be possible to update an Earthquake sized character within one frame on R800. Though it requires a bit more hustle. You split the workload in two. Half of the character is stored in VRAM the other half in RAM. The VRAM part can be updated with BMXL a 4608 bytes and in the mean time you can update the other part with R800. For 4608 bytes it should be doable to achieve this including on the fly mirroring (it takes only 4 extra cycles to swap the nibbles, and reading data backward is just as fast as forward). So 30 fps may be achievable, especially if other character is smaller.
To tackle the data space requirement, perhaps it is possible to filter out and group the sprite patterns that do not changes over frames in a smart way and reuse among frames. Also it could be worth looking into layering of sprites. E.g. looking at Earthquake the legs do not seem to change, same for the hand and chain part going up and down. Of course this will all require a lot of hustle and maybe in the end it is not enough... anyway my 2 cents if you ever serious in pursuing this 
Sprite sheets used on this demo:
