It's ok that the various linux distributions use gpg to verify e.g. new packages downloaded with http. But what happens if the server that holds the packages gets hacked? OK, they need a new gpg key, but how do they guarantee that the new gpg keys are the valid gpg keys? There is no valid gpg key until the new one gets downloaded to the client, so there is a window when the packages [containing the new gpg keys] are not "validated" with gpg keys. Is there any method to give the new gpg keys to the clients in an "authoritative"/secure way?
If only the server holding the packages is compromised, and not the private signing key, there's not much to do. The old key remains valid, and packages modified by the attacker will be detected as such. I assume your question is what happens if the signing key is compromised.
As long as the old key hasn't expired, people will continue to download the old packages, blissfully unaware that the key has been compromised. Ideally the package management tool should check that the key hasn't been revoked (I don't know if apt, yum and friends do it). However, the first step in responding to a compromise would be to stop distributing packages signed with the old key, and start distributing packages signed with the new key. So any maliciously modified package would linger only in mirrors before they are updated.
When people start receiving packages signed with the new key, they'll get an error message telling them that the packages are unsigned. This will hopefully prompt them into inquiring what is happening and trying to obtain the new key.
The compromise will also be announced in security mailing lists and in various industry news channels. So if you follow these, you'll get notice. Of course you should be wary of these as well: an attacker might compromise the list server or a developer's account and send a fake key compromise warning with a new public key that is actually for his own private key.
There's no magic bullet for distributing the new key. You need a trusted channel to distribute the key in the first place, or more precisely to establish trust in the new key. This is exactly as difficult as establishing trust in the old key. (In other words, most people will get it from the HTTP website or from an unsigned CD image.) You can get the new key from an HTTPS website, if you trust that the website (and the CA that made the site's certificate, and the browser you're using and its trusted base!) hasn't been compromised. Or if you know and trust someone who has the key, you can ask them for it.
Note that above, I'm using “package” in a loose sense, assuming a simple model where the packages are directly signed with the distribution signing key. In fact, in some distributions (e.g. all the ones that use APT), what is signed is files containing a list of cryptographic checksums of packages, and there's a two-stage process whereby the installer checks that the package has the expected checksum, and that the list has the expected signature. The principle is the same: the attacker who compromised the key would inject both malicious packages and list files with the checksums for the malicious packages, signed with the compromised key. The resolution requires restoring both the list files and the packages.
The standard process to give new "authoritative" key is through a package that is signed with the old key. If you trust the old key (and you trust GPG) then the new one is distributed in a package signed with the old one. Now, you can begin to use the new one.
The packages can be hold on an insecure server as each package will be checked for correct signature.
A problem occurs only is the packaging private key is compromised. I.e. the master key that sign all packages. (Debian SecureApt, Ubuntu SecureApt, Fedora). If it would happens once, it would be really ugly.