Color individual faces after modifier
Once you use a Generate Modifier (decimate counts as well) you don't have much control over the mesh anymore. Since modifiers are by nature dynamic, you can't change individual faces, since they might not exist in another frame.
Usually you would use vertex paint in a situation like this, but that's also not easy.
One method to cheat I can think of right now is: Use a texture, unwrap your model and make the decimate modifier respect the seams. It's fiddly, but you might get this working.