I always figured we should put advertising on the currency of exchange... seriously, just put what ever picture you want on an individual dollar bill (or a $10/$20/$50/$100) for a price you pay to the Treasury for printing it in volume. Different markets for different denominations and you could actually even target specific areas based on the Atlanta vs Frisco printing locations. The price of ads on a dollar bill could easily exceed the value of the currency itself, because of the multiple transactions (even if it's only in circulation for 21 months!) People would even buy them as collectors taking the rare ones out of circulation.

Now, of course you could put advertising on your dynamic (image updating) credit card so as you pull it out at the grocery store it reminds to get more SnackyPoofs for your lovely little Cartman at home. Or perhaps we'll be putting advertising on the blockchain so that they will mine, and we can get transaction costs down!