The whole reason the block chain exists is to prevent double spends.
If anyone finds a "safe" way to accept 0-conf transactions, without sacrificing any other major features of bitcoin (pseudonimity, decentralisation), this would render bitcoin obsolete - just through away all the blocks in favour of one big pool of unconfirmed transactions.
I don't see how why my proposed solution above doesn't work, and also why it should render the blockchain obsolete.
Maybe I wasn't clear enough; let me try again.
Say I am a customer, and want to buy a product from V for 0.1 BTC, double spend safe. I need to have *two* confirmed transaction for this purpose. Say I know the private keys for TX0out, which has 1 BTC, and for TX1out which has 3 BTC out. Both are deep in the block chain.
I will give a usual transaction to V which pays him 0.1 BTC, giving me 0.9 BTC change. But additionally I give him a transaction which says: "If you find two valid signatures for TX0out, this transaction gives the miner 2 BTC from TX1out, and 0.1 BTC to V".
Anyone care to explain to me why this would not work?