How can we prepare a nicotine stained room for painting without dangerous chemicals?
I'm not sure you'll find a product to seal stains without any VOCs, especially if you want an organic paint. The organic solvents in paint must evaporate to leave the coating on walls.  The fact that they evaporate at room temperatures, by definition, means they are volatile, hence Volatile Organic Compound (VOC).  The least harmful stain blocker my be a shellac primer.  Its basic components are resin produced by bugs and alcohol (the drinking kind). It will seal the stains and keep them from bleeding through to the top coat probably better than Kilz. You will need to have good ventilation while the alcohol evaporates, though. Shellac primer does a good job of sealing, but it doesn't have much any pigments in it, so you may need two finish coats (which you will probably need anyway).