A solid fuel is probably the safest way to go, although airborne particulate dust can become highly explosive. Charcoal is very safe to store and has a high heat output; actually has a higher fuel energy density than even Hexamine. It is relatively cheap compared to the refined fuels such as Colemans or Paraffin and can be manufactured easily using bio fuel resources in the long term. It may require looking at a 3rd world solution for your charcoal stove though, such as the designs used extensively in Africa.

Gyapa Stove is one of the more fuel efficient designs - http://www.hedon.info/docs/EnterpriseWords-charcoal-stoves-Ghana.pdf