Why is it that only the larger cloud providers are acceptable? What's wrong with one of the smaller providers like Linode/Akamai? There are a lot of crappy options, but also plenty of decent ones. If you build your infrastructure over a few different providers, you'll pay more upfront in engineering time, but you'll get a lot more flexibility.
For something like Signal, it should be pretty easy to build this type of redundancy since data storage is minimal and sending messages probably doesn't need to use that data storage.