First, you can't move an instance between subnets. Once a primary ENI has been assigned to an instance it can't be detached, so it will remain in that subnet. The best you can do is launch a new instance in a new subnet, stop it and then move the primary EBS volume from the old instance to the new instance. But of course, this will give you a new IP address.
Second, you should create a full mesh of VPN connections between all availability zones in all regions where you are creating VPCs. Thus if you have two AZs in region alfa and two AZs in region bravo you will have 4 VPN tunnels. For what it's worth these instances can also act as the outbound NAT instances for private subnets in the availability zone. There is some documentation on this configuration.
Finally, the way to avoid the single-point of failure for the VPN/NAT instances is to use autoscaling and scripted provisioning of the instances. This is so that if the instance fails, it will be immediately replaced by a new instance. The trick is that all VPN/NAT instances will need a ENI that will be re-used each time the instance fails and is replaced. This presentation from re:Invent 2013 has an overview of the process: video and slides.
Best option is to actually utilize the VPN that AWS already includes in their VPC setup. Speaking from having already set up what you're trying to do. Assuming having your users connect to a central location, like an office or data center is an option. If it's not, then an expanded version of the setup below would work, adding another VPN instance for people to connect to.
If you need the VPCs to talk to each other as well, you'd want to set up multiple VPN instances, at least one per VPC, preferably more than one for redundancy, but to do that you'd need another instance to control the failover and update AWS's routing tables with the new path.
Option 1:
A central VPN server for users to connect to in AWS with tunnels created on it to route traffic to your other VPCs. You would need other instances in the separate VPCs for VPN tunnel creation.
Option 2:
A central VPN server for users to connect to in AWS.
One or more other VPN instances per VPC set up with tunnels for connectivity to the other VPCs.
Option 3:
AWS VPN functionality to a central office or data center where a user VPN is set up.
One or more VPN instances in AWS with tunnels set up for connectivity between VPCs.
Amazon unfortunately doesn't have setups for VPN between VPCs, so in cases where I'm suggesting a tunnel, you'd of course need a set of instances, at least, for each tunnel setup.
Best Answer
For VPC in the Same region:
VPC peering, Set up a VPC Peer connection to the other VPC's. So if the vpn server is in A, creating a VPC peer connection from A to B and A to C.
http://docs.aws.amazon.com/AmazonVPC/latest/PeeringGuide/Welcome.html
For VPC Peering in Different Regions:
You can Use a software VPN like Openvpn or Strongswan
Layer 3 setup with OpenVPN
Layer 2 setup with OpenVPN
https://docs.openvpn.net/how-to-tutorialsguides/administration/extending-vpn-connectivity-to-amazon-aws-vpc-using-aws-vpc-vpn-gateway-service/
https://s3.amazonaws.com/awsmedia/AWS_Amazon_VPC_Connectivity_Options.pdf