Custom Team Colour Materials

Hello, I am using a shader that allows me to change parts of a texture to the material colour. This works great. The problem is when I change the material colour, all instances of my player object change colour, thus making everyone seem like they are on the same team (same colour).

Now the possible solution I thought of was to have a few versions of my material, called "Team 1 material", "Team 2 material" and so on. This would allow me to change team colours separately. This poses two problems, however. First, the number of teams gets restricted by the number of materials I have. Second, my character objects have LOTS of meshes (most of which use the same material). This poses a problem with how would I replace all of the materials at runtime (do I have to hard-code all mesh names?!).

To summarize:

1. Can I have material colours per instance of prefab, rather than instance of material?

2. If I cant, how can I replace all instances of a material in a prefab to another material without hard-coding all mesh names?