What about using multiple 8x8 textures allowing for shading e.g. stripes (fur), dots, dithering?
Could allow for an interesting art style and higher resolution looking textures, but maybe make for complex art pipeline with multi-material models.
Or using multiple 8x8 textures in a single character to provide a more textured effect e.g. sides of cubes, parts of characters e.g. eyes, nose, mouth, hands ect.
The result could be a low res style of game meshes.