> you either need a way to roll-back the change (which removes most/all of the benefits of an append-only structure like a blockchain)
Blockchains are not inherently immutable or even append-only. What they guarantee (assuming the consensus scheme is working) is that you'll be aware of all the data in the chain or the fact that some of it is missing; the idea that blockchains are inherently immutable is a big misconception that treats blockchains like they're magic.
In a database, if you are forced to delete data, you'll go ahead and delete that data. You's probably also record the fact that you deleted that data in some kind of auditing log to be able to audit compliance with those deletion requests, as well as detect illegitimate deletions.
In a blockchain, you can do the exact same thing, but with better controls: add a block to the blockchain that contains machine-readable instructions telling all nodes processing the blocks to delete the data if they have a copy.
Once every node has done that, even though the blockchain still commits to that data, the data itself is unavailable, thus complying with the requirement to delete it. Essentially we now have a dangling pointer: there will be a digest in the chain, but the data that was hashed to produce the digest is no longer available. The blockchain is of course no longer able to be validated in the same way as before, but what you can validate is the fact that the deletion process was followed properly. E.g. you might have rules that state 2-of-3 senior admins have to use their signing keys to sign off on a deletion request.
A similar example of this principle exists in Git: you can do a shallow checkout that doesn't contain all prior history. Recentish versions of Git handle this quite well: every operation will succeed if it doesn't happen to process the missing history. Similarly, if every git repo is in fact a shallow repo, with some history deleted, that data will gone.
At the low level, this works because practically all blockchains make use of merkle trees. Rather than the hash of a block b_n being calculated as Hash(b_n), you instead have a header that commits to a merkle tree of data items. Thus you can still validate that the headers are connected without actually having all the data (extra credit problem: is this always a good thing?).
1) By "commit", we mean that the blockchain headers contains a hash digest of some other data; the headers are committed to the data they hashed, because if that data was changed the hash digest would change, rendering the headers invalid.