architecture - Associating materials and primitive

I'm trying to find a way of setting any kind of material class on any kind of primitive class (all the material classes have a base material class, same goes for the primitive classes).

What I mean by that, is, I'm looking for a way to do something like this:

Cube a = Cube( ColorMaterial( COLOR_RED ) );
Cube b = Cube( TexturedMaterial( ambienTex, diffuseTex, specularTex ) );

Ok, so that looks pretty easy, but I've got a few problems. First of all, inside my Cube class I've got a function in which I build the cube's geometry, as such:

VertexPositionColor vertices[36] =  { VertexPositionColor( pos, color ), ... }

Because of this, I can't just pass any type of material to my primitive class, because that would mean that the function that builds the geometry would need to be able to change the type of vertex it uses. I can't use templates either, because, even though it would solve the type issue, different vertex types are not constructed the same way.

So, is there any way of associating a material to a primitive?