Well, really you're not restricted to paint with just flames. You paint with kind of a particle brush. How these particles act is up to your choice.
Looks pretty interesting to me.
http://www.escapemotions.com/products/flamepainter/
There's a demo for download as well. Full product is just 12€/15$.

I could imagine this to be a nifty tool to create textures for FX shaders.
The weakness of it's approach: the outcome is more or less accidental, depending on your settings and workflow. It wasn't designed to be used for creating textures in the first place. You don't auto- create tileable textures, either. Some first thought and post processing would then probably have to be done.
But the good news: it's able to export alpha channel TGAs in very high resolutions.

Mouse as input sucks, I feel the need for a tablet now.