Más fácil todavía, sin php, creas un fichero de texto que se llame version.txt accesible por internet (servidor web, carpeta public de dropbox...) y dentro tenga el texto de la última versión. La aplicación lo descarga por HTTP, comprueba si es el mismo valor que la instalada (la que está ejecutándose vaya) y en su caso descarga el APK.
Cuando lances una actualización, actualizas el fichero version.txt y el apk.
La periodicidad de comprobación, lo mejor es que se haga al ejecutar la app y solo si ya pasó tiempo desde la última comprobación (no es plan gastar recursos de red del usuario innecesariamente)