A multi-AZ cluster with ordinary binary log replication to another region (with preparations to launch a new cluster in that region based on that slave on short notice) might be a good solution.
Regular asynchronous replication is your best bet, with a regular run of pt-table-checksum scheduled to ensure your data is consistent.
> Regular asynchronous replication is your best bet
That doesn't get you HA in any practical form. I've done the heartbeat thing, it created more outages by itself than would have occurred with no HA solution at all, usually failed to kick in during a real failure, and we could never fix all the split-brain scenarios. Galera is absolute magic by comparison.
Hence my suggestion that a cluster be deployed within one datacenter, with asynchronous replication to a standby.
Heartbeat is very problematic, I agree, but it's hardly the only solution out there (and far from the best solution). That said, I have learned that it's remarkably configurable, so many of the problems you encountered could probably be addressed, if you're willing to learn about Pacemaker and really dig into its configuration.
I should mention that the system I'm building that uses it has yet to go into production, so others may have more experience on this than I do.