Let's assume, for an instant, that you really need to "re-key your Web servers" because of the heartbleed bug (if there is such a need, then you quite logically also need to do it for every other similar vulnerability which shows up, hence several times per year, and you must also do it for vulnerabilities which will show up, so, by that reasoning, your brand new key will be immediately toast as well). Let's also assume that re-keying is sufficient (there again, a fallacy: if an attacker could obtain your private key, then he could also obtain all your confidential data, so the problem has a much larger scope).
Under these assumptions, the model is that of a compromise of your private keys (that's what you fear). You need to do two things:
Declare the old certificate as invalid, so that clients cease to trust it. This is known as revocation.
Obtain a new certificate with a new key that the attacker does not know of.
There is no conceptual need for doing things in that order. In fact, you usually want the new certificate to be up and running before the old one is revoked. It so happens that some CA insist on binding the two operations together, i.e. revoking the old certificate and reissuing the new one concurrently (one reason for doing so is commercial: you paid for one certificate, so you should get one non-revoked certificate at any time).
Fortunately, a few characteristics will help you:
Clients do not cache certificates. In the SSL/TLS protocol, the server systematically sends its current certificate, and the client will always use that one, not a cached version.
Revocation is asynchronous: when a certificate is revoked, its serial number will be included in the Certificate Revocation List published regularly by the CA. Usually, it will take a few hours before revocation is effective (it depends on the CA policy). Moreover, clients do cache CRL, so even if a new CRL is immediately published by the CA, clients who connected a few hours ago will still operate on the old one, until it expires. (OCSP may reduce the time window, though.)
Many clients don't bother checking CRL anyway, so, from their point of view, the old certificate will never be revoked.
It still is in your best interests to complete the procedure quickly, i.e. within a few minutes. Anyway, you MUST be able to do that process properly, because certificates expires: you are just doing it early (out of a sense of deference to the current wave of ill-informed paranoia).
