Ну, думаю вы сами ответили на свой вопрос — erlang лично мне кажется лучшим выходом. Вот только велосипед писать врядли стоит — возьмите какой нить yaws (думаю, с http вам проще всего будет — yaws со стороны сервера и кучи библиотек — для андроида и вовсе встроены — для клиента).
Какой протокол — не столь существенно, хотя наверное какой нить из бинарных был б поэффективней. Тем более у эрланга неплохо с обработкой бинарных данных. Нечто вроде rest-а думаю тут будет лучше всего.
NAT transversal для сервера с белым IP вовсе нафиг не нужен. Вот если у вас сервер находился за Nat-ом сам — тогда да. Вы верно заметили — это всё больше для p2p актуальней.
А вот насчёт шифровки… Да, наверное можно и ssl прикрутить, но рекомендую TLS v2 и старше (версии младше и версии ssl не так давно поломали).
Насчёт прокси вообще не понял. Стандартные механизмы запросов со стороны андроида того же более чем достаточны имхо для обработок всяких прокси. Оставьте это дело системе пользователя, не лезьте в это.
