I think Richy is talking about trying to make bills that stay in circulation. Single-use notes work great.
Michael_S has presented a practical solution for making single use notes safely on a PC, with QR codes and all. This thread, and other threads around here, abounds with beautiful artwork for notes. The two steps away from this to distributed (as in anyone owning a PC and some bit coins) issuing of bills for circulation are: 1. tamper proofing of what´s hiding the private key, and 2. measures to prevent counterfeiting of the visible parts of the note.
1. A solution already exists in that of scratch card lottery tickets, and I can´t imagine applying a rubber coating on plastic will require a lot of investment in equipment.
2. This is likely to be the most tricky part for an economical distributed solution, so I will assume a partial centralization is required. Like that of small banks getting their token credit cards from a central manufacturer, for then stamping the cards themselves with an account number and so on ( I assume this is the way it is done. This central producer of blank bitcoin notes will be able to counterfeit, but this event will not effect the holders of genuine bills (as they can be redeemed to online
BTC)
And maybe there is a point 3. Preparing for lawsuits after the government gets wind of it...