One of the things I do for my customers is design redundant Internet connectivity. Most of the enterprise-grade options are probably not available to you.

Some people I know get service from two providers (phone and cable) but that might be too expensive. I'd also want to find out how reliable the two providers have been in your area during storms.

Satellite Internet (as suggested by duckear) is very reliable, except when there's a lot of water between your antenna and the satellite. Very heavy rain or snow can temporarily keep it from working. The latency and bandwidth are also pretty poor.

Cellular is more reliable where I live than landline service, but that didn't work for you.

A local wireless ISP may be your best bet. You'll likely need an external directional antenna, if service is available in your area.