Earlier post show creating GRE tunnels between ubuntu machines, But if they are behind firewall or cloud they will be natted. In this case we need to use private ip instead of public ip in /etc/network/interfaces file.

See how to configure gre behind nat. below link shows you how to modify configuration just samll modification,  In the below link Machine-B is behiind NAT so i replace public ip with local ip assigned to the interface. Just do the same for Machine-A also in your caes.

http://geekinlinux.blogspot.in/2014/02/gre-tunnel-between-vm-in-cloud-and.html