на клиенте поднимаешь openvpn сервер.. настраиваешь маршрутики, с андроида соединяешься к нему и так же настраиваешь маршрутизацию, что бы vpn не был маршрутом по умолчанию. Если сильно хочется прокси, то ставишь прокси на андроид.. либо nat.
у клиента должен быть белый ip.. статический или ddns