This is a major concern of mine as well.
For some purposes, there's a need for a single identifier. For others, various counterparties only need to agree that they are talking about the same party. Creating paired (or multi-part) keys might work for that. (This could also cut down on the rampant and promiscuous data exchanges that occur currently, particularly if the subject of the data had to participate in the making of any such shared identifier.)
For the general case of online identity, I'd really like to see the concept of an identity manager, with various policies which could be set, both as defaults and with specific counterparties.
As an example, I might have a policy that "all sites default to a one-time session identifier which is destroyed after 24 hours". This gives a stateful history for 24 hours, but a clean slate afterwards. It should be enough for basic site navigation, but not for deeper interactions (e.g., posting inane comments to HN). The periods might be longer or shorter.
For a select set of sites, persistent IDs might be presented, but specific only to a given site.
And where necessary, a set of sites might have a common ID. Say, a cluster of systems used for work purposes.
And if needs be, you might have a limited set of systems -- your government pensions account, tax systems, and voting registration, say -- which link to a specific government-issued ID.
For such a system, I see a physical token (I'm partial to very-near-field chips in a worn form-factor, say an NFC-ring), some additional input (password, passphrase, possibly biometrics), and then, by way of an identity management system (probably on a local device), the identity assertion specific to a given service is offered.
There are any number of other elments to this, including the problems of deanonymising data and such. For that I see legal reforms coming into place, which is a longer discussion.