This is a great question that unfortunately doesn't have a good answer. Ignoring the question of backups, GDPR's requirements have the implication of imposing a workload on database engines that, in most modern architectures, is either pathologically expensive or not currently possible. Some companies are approaching this from a "best effort" standpoint rather than conforming to the spirit of the regulation because the technology simply isn't there to make it feasible for some cases. I've been working on this problem for the last year and this is (IMO) a major gap in the regulation; it presumes that something is possible that isn't for existing applications that are otherwise universally viewed as harmless and permissible.

Scalable database engines that can support the letter of the GDPR in terms of data handling don't really exist. This is not a problem that can be trivially solved by patching an existing database engine; the requirements of strict GDPR data handling violates fundamental design assumptions of common database architectures. If you look at, for example, high-assurance databases which have a similar set of requirements for data handling as GDPR, they are never used when at all possible because their performance and scalability is terrible. (These databases are conventional architectures with GDPR-like data handling controls added.)

A database engine capable of strict conformance with GDPR while maintaining vaguely comparable performance and scalability relative to what we are used to would require a comprehensive new database engine design from first principles. This is something only a small number of people are capable of designing and implementation would be a very substantial engineering effort. Possibly a business opportunity -- one of the reasons I've been thinking about it, having worked on high-assurance databases in the past.

Purging a user's data is probably a matter of writing a short SQL/Python/Bash script for most databases (don't forget the audit tables, though it kind of defeats the purpose of audit tables, but whatever). It's something I'd only do on request (I'd expect it to be a rare occurrence), certainly not going to automate that sort of thing.

I'm not about to go risk corrupting my backups trying to scrub old customer data out of them. Perhaps only keep the last X days of backups and let the paranoid customer's data attrit out naturally?

With a documented data retention and deletion policy. You don't need to keep your DB backups forever, and a request to delete someone's data comes with some reasonable amount of leeway as to how long it takes you to delete it. Obviously you can't drag that out for a year, but from what I've been hearing, a month or two isn't unreasonable.

If you're doing DB backups daily, expiring backups after a month (or even, say, two weeks), should be no problem and not an operational risk at all.

One approach may be to tokenize user information. Ensure that any personal data is separated from other data and mapped via tokens and kept in one place. Handle backups of this database with special care.

You can then have the rest of your systems work as normal.

All this is easier said than done if you have a large investment in existing systems, but it is probably a design approach you can enforce from the beginning if you are a startup.