Interesting. Have you tried using a DNS tunnel? It would be similarly slow if it worked over your connection.
Yes, both ICMP and DNS tunnels work on most of the mobile plans here (I'm from Paraguay, South America).
We had an interesting experience with the Internet.org campaign, they signed an alliance with the biggest telco (Tigo - Telecel, Millicom International), so all the users are getting free Facebook access. This small project I'm trying to code involves a critique to the Internet.org campaign ("free Internet for poor countries"), Internet != Facebook.