I like the idea of physical Bitcoins, but I think paper isn't going to be very feasible. No matter what system you come up with to try to secure the keys, someone will find a way around it. It is like DRM in a sense: you're trying to stop "the bad guy" from copying information (the private key), while still letting "the good guy" access it. Difference is instead of "the bad guy" being someone who wants to copy music they paid for, it's someone who wants to copy a key before passing now-useless cash on to some poor sap.
Never underestimate the resources, smarts, and time crooks have to dedicate to their work, especially when it involves essentially stealing money (from the sucker they pass the bill to after copying it). There are a few of us and thousands of them who'd love to be able to give themselves free money.
That's not to say I don't think we should even consider some kind of physical/printed currency. I just don't think it'll be as simple to prevent fraud as some seem to think.
What I think would be more feasible and useful is using SD cards and USB sticks as coins and wallets. These days you can get 32GB of each for under $100. For use as coins you'd want not one large card but many small ones (even 1MB should be plenty) - probably everyone has a few laying around, and for such small sizes I'd imagine they'd cost only a few cents each.
For coins, you'd put a private key (or a few) on a card and hand it out. To redeem the coin you put it into your PC and copy the key into your client. SD cards are roughly the size of a coin and just about everyone has a reader for them (and if not they're cheap and have many uses) so this works nicely. MicroSD is a bit small (easily lost) but has some advantages like being usable in modern phones; keeping them in the plastic case they come in could help with the size issue.
For wallets, you'd put a few coins into a wallet file stored on a USB stick. You could hand those out too (like "bills", being physically larger than SD cards) or use them like a bank card - put the stick in, transfer a few coins.
Advantages of this are that you'd be using ordinary SD cards and USB sticks, that are too small in capacity to be of much other use, can be "refilled", and can hold other data besides just the coins. So you could include some notes or media with a payment. For example when paying your bills, just send in a card/stick containing the balance and a text file holding your account number. (Granted if you can pay bills in bitcoins, you'd probably do so over the Internet, but anyway...)
Obvious problems:
1) People can still easily copy the coins and then hand them out again.
2) A merchant can copy your entire wallet when you put the USB stick in to pay.
3) While small-capacity cards would presumably be cheap, nobody sells them anymore.
4) Being given an SD card or USB stick, you have no way to know if it even has any coins on it.
#3 I think is the big thing here. While you can walk into your favourite overpriced electronics store and buy a 32GB card for not much, you can't buy 32768 1MB cards at all. Nobody makes 1MB cards anymore.
What you'd have to do is start up a small business selling small cards/sticks for just this purpose. I imagine you could convince a manufacturer in Asia to make you a few thousand small ones for not too much, which could even be stamped with the Bitcoin logo. You earn back the cost by starting up an exchange; someone sends you some amount of money (plus a few cents to cover the cost of the card and postage), you send back a card with that amount on it.
Now, if you already have these cards being manufactured for you, you can go on to add some security features. Say, reading the card destroys it, or the card comes encased in something similar to their plastic cases which must be destroyed to get at the card itself (so you know a card not in such a case is no longer valid). Those ideas kill reusability, but I'm not coming up with any ideas that don't. Ultimately they'd be more like checks than coins, and nothing stops someone from writing you a bum check either.
For "wallet" USB sticks, the most secure thing to do would just be to keep only a little in it at a time, so that anyone who copies it won't get much. Of course that isn't very convenient. What you might have is a stick that unfolds to expose a simple numeric display and keypad, where you type in a balance, then press OK, and it allows only that much to be taken out. One way to do this would be to make "change" - store several keys worth 0.5BTC, 1BTC, 5BTC, etc, and it passes on to the reader only enough keys to make that balance (rounding up if necessary), just like you'd give a cashier only enough coins to make the balance (but if you don't have any pennies maybe giving a nickel to cover the last 3 cents).
Having such intelligence in the stick itself would of course increase its cost, but you'd only need one - you wouldn't be handing these out to people like you would with coins; they'd function more like a bank card.
You could eliminate the need for a lot of complexity in the design by just having it emulate an ordinary removable disk, with one partition where you can store files like any ordinary disk, and one reserved for the coin keys. When you hit OK, the appropriate keys are readable from the raw partition (no filesystem) and removed from memory on read. Writing a program to handle this on a PC would be dead simple. The device could also be powered by the USB port itself, reducing a lot of physical complexity.
I think no matter what you do, it's going to be somewhere between difficult and impossible to make physical bitcoins that don't carry the risk that they've already been digitally spent (or if you use SD cards, that they don't actually contain coins at all). It boils down to being given an object which is said to have value, but which becomes worthless through an action that can be done without physical access to the object. You have to trust that they won't do that, because there's really not much you can do to prevent it. I also think the future of Bitcoin for in-person transactions is in smartphone apps, not distributable tokens. But if you could make tokens and smart USB sticks work, that'd be pretty damn cool.
