One huge issue is your final image has to fit a plane of 16*16 tiles, with 15 colors per tile.
You could overlay 4 of thoses planes on the hardware.

And everything has to fit 256 palettes, keeping in mind you can't change all of thoses in a single vblank.

Good luck with the algorythm