At that point, as long as you trust the cryptography and tamper-resistance (of mint hardware and coin hardware), you can trust that a coin someone hands you is valid.
It's probably about $5-10 to make a "coin" with these properties, and $200-300k to make a mint. There are a lot of hybrid online/offline token based currencies which would meet the requirements, but assuming the right hardware, you can build the whole thing as a wrapper around arbitrary data.
There is still no real market for this, though.
The moment I start circulating them, this now means that everyone who wants to accept these coins needs to destroy them, reveal the private key, and transfer those coins.
That defeats the purpose of the whole tamper-evident system - the idea behind it is so that they DON'T need to be redeemed.
http://lesswrong.com/lw/ne/the_parable_of_the_dagger/
They are _not_ instantly verifiable without destroying the coin.
At that point, it becomes necessary that all of the other physical tokens in the world must then be immediately destroyed on redemption and validated as a normal network spend... Which defeats the purpose of these transferable tokens to begin with.
The tamper seal doesn't help. You might as well just print out your own private keys as QR codes, the person accepting them will need Internet access to verify+transfer them, just as now with these "tamper-evident" systems.