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 like this approach too, but I'd add a site address in addition to QR code. The larger majority of population don't have QR scanning phones. I think this method could work, although the rate of spreading the message would be much slower I'd think than the more interactive game.