Где и как развернуть backend для Android приложения?
на стороне клинета оптимальное решение retrofit
бесплатный сервер уже на 600 юзерах может быть проблемно, лучше воспользуйтесь vds 
на стороне сервера если хочется java то spring станет не плохим решением
также многие  рекомендуют parse.com но я не пробовал, ничего не скажу
Для своего не большого проекта развернул , на python сервер , для REST API  . Дальше посматриваю в сторону parse.com .