Hey ich benutzte auch ein Android ohne installierte Google Dienste (Xperia V mit CM12) und ausschließlich FDroid Apps. Es braucht oft eine ganze Weile um sich zum ersten mal zu orten. Mit dieser App
https://f-droid.org/repository/browse/?fdfilter=GPS&fdid=org.fastergps bilde ich mir ein das es etwas schneller geht.
.