Embed the token into the cards. They don't have a significant cost these days, and it would make the cards significantly more secure. Yes, it makes the cards more expensive than a piece of plastic and a magstripe, but really, it's not THAT much. Particularly when amortized over all the cards in circulation.
If you're going that far, you could also include the PIN entry keypad on the card and use a secure link to make it nearly impossible for an attacker to get your PIN via the capture device.
And, if designed properly, they won't wear out as fast as the old style ones, and they are more secure, so don't have to expire as often. The real expiration is on the CC company servers anyway, and checked when you try to use the card.
The really painful part isn't the cards really, it's the readers. And internet transactions, but that can be handled reasonably if you have a display on the card. It can show you a bunch of numbers to type into the computer after you tell it how much you want to allow the merchant to charge you. Generates a time limited code (one use, good for one minute?) that allows the transaction to process.