Hi,
yes the solution is to use GRE tunnels on both MPLS and internet clouds. Run any routing protocol and it will reroute around failures.
For the VPN you can or can not uses the PIX, (2801 support hardware encrption with adncaced ip service image), but the GRE tunnels must be terminated on the router anyway.
Hope this helps, please rate post if it does!