You can't get black
While it is possible to achieve different ranges of colours depending on temperature of the flame as well as combustible material, fire's still light.
Light is bound to the spectrum of visible wavelengths. And there is no visible wavelength for black.
Addition1: It is important to understand that the light of fire is additive. Hence if you'd want to go towards black fire, you'd actually have to find a way to remove light-sources from a) the fire itself and b) its surroundings; thus creating a space that absorbs light.
But what colours of fire can we have?
Looking at pyrotechnics we can achieve the following colours by e.g. burning different metal salts:
Chart of what substance creates which flame colour - found on http://www.compoundchem.com
These colours are achieved, as already stated, by burning salts. As long as we know where to find metals, we can dig them up and refine most of them with as little tools as a vat of acid and some patience.
The most accessible of these would probably be:
- Lithium
- Potassium
- Calcium
- Copper
- Iron
- Lead
- Zinc
1Thank you Slipp D. Thompson