Yo, en principio y salvo otros inconvenientes que no preveo, bajaría las apps de Google desde la web de apkmirror. Están todas y sus diferentes versiones para todos los móviles y además se suben a esa web antes que a la Google Play.
Ignoro si el estar o no certificado por Google pueda suponer algún problema, pero no creo.