Is there a standard that could verify an apk against a certificate? ... or an I just describing building an alternative play store?
On Android, APKs are almost always signed by default (even if they're only self-signed).
If you update the application, Android will check that the certificate of the current version matches the one from the update before allowing you to install it.