http://www.androidcurso.com/
En realidad no es un tutorial, sino un curso, pero muy completo y recomendable.
Yo lo hice bajo la plataforma miriadaX, pero por ahora no parece que lo vuelvan a repetir.
Pero es posible que ya se pueda hacer el curso directamente desde esta página y de forma gratuita, al menos el de primer nivel.