Через системные пуши. Ты когда авторизуешься у себя в приложение отправляешь на сервер токен для пушей. Когда тебе кто-то написал сообщение, то сервер отправляет по токену команду и у тебя на телефоне появляется сообщение. По клику на него открывается приложение и начинает уже стучаться к себе на сервер, за этим сообщением. Естественно, если у тебя нет сервера во внешней жизни, то ты в пролёте.
Нет, ты конечно можешь держать сервис в фоне с открытым портом, но в текущих реалиях андройда их прибивает система на право и на лево.