I thought about doing something like this a while back, but as ever didn't get chance to play with the idea. For me, the trick would have been to say screw it and randomly/genetically generate the code required to change the palette. On modern CPUs it shouldn't take more than a few hours to generate/simulate even if you're brute forcing it.
Now, of course, once you get to dithering the image and optimizing that, you're starting to explode the solution space but it's not exactly insurmountable. (I've got a 2 year old daughter and enough work to sink a battleship these days, so unfortunately as much as I hate to say it, I think my SAM programming days are done :'( ).
