I think the main problem is difficulty. There is one, single, global difficulty for the whole network. It is convenient when it comes to validation, but it is very inconvenient if we take mining into account. Because if we have one million miners and the whole difficulty is one million, then (assuming that all miners have the same power) each miner can produce one block with difficulty one per ten minutes (on average). So, my idea is using more than one difficulty and combining all of them to get the whole network difficulty.

So: each miner will start with difficulty equal to one. In this way, even CPU miners can start mining in this system if they really want. Then, each miner will calculate its own difficulty just by competing with itself. Each miner will know, which target should be used to produce one block per ten minutes (on average). And then, each miner will produce single block header per ten minutes that meets that miner's target.

Finally, hashes will be added in a way that respect their difficulties. So that any two hashes could be added if (and only if) their sum is divisible by four. Then, it can be divided to produce block hash that respect the difficulty and is equally probable to some other miner working alone.

Some example:

firstMinerBlockHash: 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f
secondMinerBlockHash: 000000006a625f06636b8bb6ac7b960a8d03705d1ace08b1a19da3fdcc99ddbd
sumOfHashes: 000000006a7c356eff73e69811feb49ddcfad40b6170af73145195b3d726c02c (always divisible by four)
finalBlockHash: 000000001a9f0d5bbfdcf9a6047fad27773eb502d85c2bdcc514656cf5c9b00b (sumOfHashes divided by four)

In this way, shares could be combined in a decentralized way. It is the best I came up with so far, but I think it is a good start.