Вам нужно определиться с угрозами от которых защищаться.
В любом случае свой трафик Вы подставите VDS хостеру.
Будете хостером подставите магистральному провайдеру.
Ставьте OpenVPN. Для него есть клиент и под Android.
При настройке не забудьте про DNS leak. Желательно "зарезать" на вашем Firewall на компьютере или телефоне любой исходящий трафик куда либо кроме IP адреса VPN сервера. А то бывает VPN специально "уронили", а Вы и не в курсе, что роутинг выпустил весь трафик через обычное соединение. Интернет то работет.
А для того чтобы радоваться жизни, у Вас уже всё есть. :)