Sólo necesitaba hacer esto y fue bastante fácil usando este método:
Instala IFTTT (aplicación gratuita que admite todo tipo de reglas increíbles).
Crear un nuevo "applet" donde:
Si esto: comprueba los mensajes de gmail según los criterios que quieras
Entonces eso: enviar notificación
Estoy haciendo esto para tratar de obtener mensajes de intercambio del trabajo (pero no puedo acceder o enviar contenido fuera del trabajo). Terminé creando una regla en outlook que envía un nuevo mensaje a mi cuenta de gmail con un asunto/cuerpo establecido (a través de un script). IFTTT busca los nuevos mensajes con ese asunto y aparece una notificación.
He utilizado esta página para ayudarme a crear el script para crear un nuevo mensaje: http://www.slipstick.com/outlook/rules/send-a-new-message-when-a-message-arrives/
He visto que no confías a Google tu correo personal. La cuenta de gmail que usas podría ser una cuenta ficticia (asumo que ya puedes hacer esto ya que estás en Android). O podrías utilizar un activador alternativo de IFTTT.