You are correct that flash paper is a form of nitrocellulose, but it is one of the more stable and safe forms.
Since one of my hobbies is magic and I work part time in a magic shop, I am very familiar with stage flash paper. We sell it in 9 by 10 inch sheets for $2.50 per sheet. It is quite safe if kept away from extreme heat or flame. In other words, it is no more dangerous or combustible than the black powder you are using in the pistol.
It has the thickness and strength of the kind of tissue paper that one uses inside gift boxes--maybe just a bit stronger and certainly stronger than cigarette paper.
The advantage is that it is completely consumed when burned leaving no ash what so ever.
Although I never used it for pistols, I have used it to make combustible powder bags for small scale cannon and I got the idea from an article written up in some muzzle loader magazine years ago. The article I read at that time was describing to make combustible cartridges for use in percussion revolvers--to actually resemble those that were made commercially back in the mid 19th century.
Several of my small scale cannons are large and heavy enough that lifting up the barrels and carriages to load black powder like one would do with a rifle is a bit cumbersome. Making small powder bags that I could simply insert in the bore and ram home from a horizontal position solved the issue.
There are several tutorials floating around the net using nothing more than standard cigarette paper, but they all have the disadvantage of possibly leaving some unburned paper behind.
However, I found this post on another forum describing how to do it with cigarette papers that have first been soaked in potassium nitrate (saltpeter).
I am assuming that this also causes the paper to be completely consumed, so if one does not have access to flash paper, this would probably work as well, but does have the disadvantage of having the extra step of soaking and drying out the papers before use.
http://www.theopenrange.net/forum/?topic=326.0
Generally, the paper part of cartridge is constructed in a tapered cone shape so that when the cartridge is seated, the paper shell breaks open inside the chamber exposing the black powder to the flash from the cap. If using flash paper, the cap would probably ignite it anyway, but I don't know about the paper treated with potassium nitrate.
Cheers