The most stable paints will be made from ground mineral pigments. Plant dyes will change color over time.
Charcoal is good for black. Soot is 10 times better. Artists call soot "lamp black".
Rust is good for, well, rust. You can try heating the rust for a different shade.
You can get various brownish colors from good 'ole dirt. Mix with oil for a darker color.
These three colors (black, red, brown) are the most common colors seen on Amerindian artifacts, for obvious reasons.
For other colors, the easiest thing to do is go to your local supermarket and cruise the juice isle. You can find mostly purples, reds, and oranges there. Cruise the condiments isle next. Mustard makes a great yellow dye.