I like the idea of a small sticker with a QR Code. Stickers aren't expensive to produce and ship, plus the notes stay clean.
In my opinion this should be crowd-funded, i.e. each person puts a few bitcents on a few bills and hands them out to strangers. The idea is not to get rich, but to metaphorically use fiat money to spread the word about a new kind of money. With crowd-funding there is no need for complicated means of verification via IP/email/whatever, it's first come first served.
I think you'll get a lot fewer people participating when they have to put the money in themselves though. I know I wouldn't. It's not that I don't want to see Bitcoin expand, it's that I don't want to be at a net loss for doing so. And I think a lot of other people are as... stingy... as I am in that regard.
If it can be done for free, there will be a lot more people participating.