Layered Billboard Sprite

My project requires billboarded sprites in a 3D world, (similar to DOOM II) that need to be composed of multiple layers composited together, with each layer colored separately. What would be the best way to do that?

My first 'solution' involved creating a new texture at runtime for each sprite, and compositing them when needed, in a very slow operation. This can't be the best way to do it.