How about having the first tile in the tileset reserved for the sprite's palette? Hmm discussing a new tileset type without the game even being developed...