It's possible to design a blockchains that don't require brute-force computation. Bitcoin uses a "proof of work" algorithm, but Peercoin (for instance) uses "proof of stake" which is a lot less CPU-intensive.
There's an interesting primer on the subject here: http://www.truthcoin.info/blog/pow-cheapest/
You can still get the benefits of verifiability, append-only, detect misbehavior etc without it. See for example Certificate Transparency (RFC6962) for a standard that implements those properties using similar Merkle Tree constructions.
Disclaimer, I have a startup that generalizes the same Verifiable Logs (and also allows for Verifiable Maps): https://www.continusec.com/
For example, in the case of certificate transparency, that the CAs aren't mis-issuing certificates, and further that the logs aren't conspiring to hide entries (such as via split views).