Having two cloud providers would work assuming they don't share any critical infra-structure and assuming that it is not the same set of employees that have access to both systems. Also helps if you have a totally separate set of credentials for the back-up system and if that back-up system can only be unlocked by very senior people (preferably execs) after a catastrophe of suitable magnitude hits.
Whether you store your primary in the cloud or your back-up in the cloud the story is the same: have a copy somewhere else.
Finally: the only real back-up is one that is off-line. So from that (ok, ultra-paranoid) viewpoint it would be best if you actually went to an off-line medium to store your data in such a way that nobody can wipe it all out without physically destroying all copies.
All this of course after suitably weighing the importance of the data.
Though if we unbox that a bit... How do we balance the risk of loss due to your cloud being owned vs. loss due to the risk of your users' PII being violated if someone attacks your in-house (ostensibly in-house reliability and security-managed) copies? Better make sure you're spending the money on security best-practices on all your copies, not just the "live" ones.
Side-note: What are your thoughts on two separate cloud providers as providing sufficient insurance? Say, having your data live in Google Cloud and at rest in Amazon S3?