(I voted no.)
Let's cut this down to the core of what is wanted here: [...] some sort of distributed public database with some kind of cryptographic controls to both timestamp, certify that the information has not been tampered or modifed unless through proscribed rules and protocol, and that effort to store the data be associated with Bitcoins so far as charging for either access to that database or more importantly to put information into that database.
That is my understanding. I think Bitcoin can do this already, with no bloat in code or protocol, no scripting and minimal data in the blockchain. I wrote about it over on
https://www.bitcoin.org/smf/index.php?topic=1938.msg26342#msg26342 but maybe not very clearly (please ask if interested).
Bitcoin provides timestamping. If you make a transaction which includes (e.g.) a sha-256 of some data then it becomes part of the timestamped chain.
Other systems must maintain their own sets of data (monotonic chain or otherwise) with their own P2P system and rely on Bitcoin only to timestamp it, and prove a simultaneous spend of >= 0 BTC. The reason to use Bitcoin this way is to avoid fragmenting the proof-of-work effort, which benefits only the cheaters.
The perception and growing consensus is that the only way to accomplish this task is to shove it all into transaction blocks. If you can find another solution to this problem, I'm totally open to a solution. The best alternative is a separate block chain and hence independent currency which as creighto and others have suggested is not likely to succeed.
My suggestion would put a
small amount of data into a small transaction. The txns to do this will include fees to get into the chain regularly and promptly - maybe the transaction consists only of fee? Heavily used systems might want a timestamp every 10 min, so that makes one txn per external service per Bitcoin block. Aggregating these into one txn per block looks like a service the market might provide.
This is not taking charity from the original Bitcoin, but buying a service from the miners. The only extra requirement is 32 bytes of message on the transaction; I think this is necessary for purchasing from an online retailer anyway.