Sounds like your carrier is blocking the VPN's, and if that is indeed the case, you're probably boned unless you find one which isn't blocked. Have you tried (A VPN) with a regular internet connection over WiFi (rather than over mobile data) to see if you can get around it that way ?
Have you tried US proxies ? (If you haven't, Google). From memory there are a number of apps which will 'proxify' any app that uses the internet (this can bit a bit hit or miss so far as whether an app will actually work this way or not though, like Orbot mentioned below). Also, keep trying VPN's; there are literally dozens (at least), if you want access to US GP badly enough, you'll try as many VPN's as you need to in order to achieve it. I know trying 5, 6, however many you've tried is a lot (and normally it would be), but you may have to try a lot more than that given your circumstances.
You could also try Tor; Orbot specifically - I have no idea whether GP will work specifically through Orbot in this way as I've never tried it (I do use it regularly on my phone for a bunch of other stuff though), theoretically it should though; any app that accesses the internet
should be able to be made to route through Orbot/Tor; doesn't always work that way/easily though.
You'll need to manually configure Orbot to use a US exit node (which is relatively easy enough to do, Google for how to do this).
So...You can probably achieve this, but it depends on how motivated you are to do it. I understand a number of Middle Eastern countries impose all kinds of restrictions on the internet/telecoms, so based on what you've said, you're obviously going to have to work your way around them.
Edit -
This page has instructions on how to configure Orbot to use exit nodes in a specific country only. Fairly simple. Again, whether it works or not, no idea as I've not tried it, but looks pretty straightforward.
