I am having a similar problem. the dynamic IP address that my ISP allots to me is not ICMP pingable and hence tunnels are not working. my ISP tells me that i will have to pay Rs 250/month to get a static IP address and only then it will work. not sure if this is the right way to go about it
You don't need a Public IP or a Static IP. You can communicate on UDP in a NATed environment. Your ports should be open. ICMP also not required.
i know, but the ISP wants to extract money from me. Hence they refuse to allow UDP traffic in my NATed environment ... typical vendor cussedness
I feel if you are on a NATed IP, still you can use Tunnel Broker. However I hope your firewall is not blocking all the ports.