If you use the right palette entries I believe it's possible to have a working textured background with 16 or even fewer palette entries used, though it will repeat infinitely instead of fading (which is what I wanted my backgrounds to do anyway). If not, it still allows the use of a second textured background with some freedom in colors. Though both would require a fair amount of precision to pull off and it's all a moot point anyway since those are never going to get used.

edit: come to think of it, I believe it can be done with any textured-background-safe palette entries, with sufficient fiddling