custom texture format

I’m rendering a large amount of (triangle) geometry with textures applied.

My textures are unusual: instead of using the whole RGBA domain, I only need something much more limited: a single-byte indexed color, and an alpha channel.

In other words, the color at any given point on my geometry can only be one of 255 predefined RGB colors (I’m using some gradient palette). In addition to that, I need 255 bits of alpha.

Now, looking at these requirements, in an ideal world where everything is possible, I’d have a custom texture format, that only contains two bytes of data per texel. Then, somewhere in my shader, I could retrieve these two values, and compute the desired RGBA value from them.

Is something like this possible?
My geometry is large, and the textures are all unique (but restricted in the color value, as described above). I’m wondering if I can reduce my texture memory requirements by half effectively.

(I hope the description above makes some sense, if not, I’d be happy to explain in more detail)