I also was talking with Evil Steve about his awesome texture-management system (essentially implementing a texture palette), and I have to say, it would be awesome to have something like that. The only hurdle really is getting OpenGL to render to a texture, which is a pain.
After about 20 minutes of Googling and digging around the redbook, I found a really good solution - glTexSubImage*() class of functions, which are designed to copy a block of pixels from system memory onto a texture in video memory. Which is perfect for what we want to do! Hooray!
Now I just need to look up a couple more things, like how to get the maximum supported texture size of the hardware, and maybe some data clustering algorithms or something. I've got one in my head cooked up that I'll jot down later and see if it works on paper.
But yeah. Hooray Steve!