Have N self-appointed archivists publish a timestamped record of the blockchain. Any query can then be based on N of these archivists.<p>I'd imagine such a record to be: the final block header, and a Merkle tree root hash of every block using a more time-resistant hashing function.
The Merkle tree root hash prevents rewriting the chain later through brute force. The actual consensus mechanism has prevented wrong writes.<p>Timestamping could be done by publishing in newspapers, or in other blockchains.<p>The biggest issue comes at the moment 'archiving' is announced. History-rewrite attacks then suddenly become a lot more valuable, so you'd probably need to say 'We are archiving the chain as of 100 blocks ago'. This prevents anyone from mucking with the end of the chain, but comes at the cost of discarding the last 100 blocks.