For this to happen, other currencies need to run on a similar model to bitcoin, i.e. blockchain and all.
What about indeed using a second block chain? One could for instance imagine such a p2p distributed Exchange where you trade bitcoins for namecoins.
Well, that's what I was suggesting. That the exchange have its own block chain made up of buy/sell combinations, perhaps with each ID secured by a GPG key if needed.