А ping работает при попытке пропинговать домен какой-нибудь или ip адрес? Домены то резольвятся? А то по описанию смахивает на проблемы с dns.

Timeout != host could not be resolved. У меня именно первое.
Но через консоль работает вообще всё - и пинг, и резолв.

Вроде, на андройде есть приложения, которые позволяют указать свои собственные dns сервера (от гугла, например 8.8.8.8) для инета через сотового оператора. Можно попробовать ;) Я бы еще настройки apn и прочую лабуду из этой вкладки поискал для оператора. Я помню в ОАЭ у меня тоже инет сам не заработал как надо, пока руками не прописал apn и не поменял какой то там параметр в настройках типа подключения.

Есть. Но я повторю - дело не в ДНС. Через браузер даже прямой доступ по IP не работает. А через консоль работает.
И раз работает через консоль, то дело не в APN должно быть. Который я тоже сбрасывал.

А wget из консоли работает?

Да, оттуда всё работает. И из-под ВПН тоже всё работает, включая неконсольные приложения.