For us this is also a very stressful situation, because if the worst case scenario becomes a reality...
"Some customers will be required to reach out to (some or all) of their customers to have them re-enter billing information."
... we can spend days contacting clients to get the payment credit card (which in some cases they should go to their boss for), and go through the billing process again, only to hope to get the list as near to a 100% recovered as possible.
Time for Billing Provider Redundancy?
This is nothing new. In higher risk industries, spreading risk over multiple billing providers is a fact of life. Like any system, if you rely on a single point of failure, then you are electing to take that risk. It's part of the price you pay for not having to deal with all the various requirements of PCI Compliance, as well as actually managing all the billing. The freedom to move from one biller to another biller seamlessly comes at a cost.
It's not an easy problem to solve, regardless. Not from a technical standpoint, mind you.
The only way I've seen this done was segmenting by cohort or product -- i.e. recurring billing on one platform and one off billing on another.
I have seem multiple payment providers where you capture billing information each time, or where you are PCI compliant and keep the billing information yourself.
You become PCI compliant! That's the price you pay. Or you ignore PCI compliance and risk it. You probably wouldn't be surprised to learn that this is far more common then people will admit (and I'm not even talking about people in high-risk industries).
Anyways, there are a few ways you can do this without having to deal with PCI compliance, though it doesn't solve the problem as well.
First, you set up multiple merchant accounts. That way, for a normal transaction, you might send person A to provider A, and then person B to provider B, and then person C to provider A, so on and so forth. The goal here is to spread the threat over more than one provider. You don't just allow PayPal, and if PayPal starts receiving too many transactions, you remove it as an option for a while.
If you are limited as you mention to PayPal, Google, and a real payment system, the best way there is to offer encouragement to use one system over another. Which ever system you want to encourage use of.
You can also find a PCI compliant provider who you can then attach merchant accounts to. They handle the PCI compliance, you provide the merchant accounts.
Of course, none of these solutions are really as easy as just using PayPal. But then you start to see why PayPal is so popular. It's downright easy.
edit: Jeez, I get it. HN doesn't like puns