Decoupling doesn't seem like the hard problem to me.. I.e. if you somehow have a separate SETI chain of verified claims about the hashes of sectors then it is easy to change the satisfiability problem to one where you need to buy your solution to the transaction chain hash as an inclusion a reference to a portion of a cycle in the other chain (which determines the payout of new coins, leaving you transaction fees.)
The problem is you need it to be expensive to change a block, so the seti work needs to depend on the transactions it signs, else it is too cheap to produce modified block chains.
Using the transactions to make a block hard to change is the best option for a self contained chain with no other work, but a chain of work/work verification seems like it can be decoupled from monetary transaction chains or anything other than the transactions in parties proving and taking credit for pieces in the real work.
The difficulties should be pretty normal. Past blocks need to influence new cycles such that the current chain doesn't speed up work for building a new alternate, etc.
If a chain needed to pull a satisfactory reference from the Bitcoin chain and reward the transaction parties its new coin that wouldn't change Bitcoin's status which is either backed by it's own Bitcoin transactions or not.
Therefore, I see no need for tight coupling between real work chains and coin chains to start making rewarding real work a social requirement/pressure for any new coinage.
