StartSSL [1] and COMODO [2] still offer them (of course, there's still the CA compromise issue you mentioned). Keep in mind, however, that a hierarchical, centralized trust model can still be useful (e.g. in medium-to-large organizations, where having an internal CA and delegating identity verification to a few knowledgeable employees is more practical than having everyone build a web of trust).
Encryption is also supported via a browser plugin, so it's not necessary to upload the private key to the server. Regarding your questions:
1) yes, you can revoke the key by generating a revocation certificate and publishing it on a public keyserver (of course, your correspondents would need to refresh the public key from the keyserver to know it was revoked, which is something they might not do);
2) sent and received messages from the past, unfortunately, are readable by the person who is in possession of the private key, if such key is not protected by a strong password;
3) yes, you still need the old private key to read the old messages;
4) you can generate a master key (to be kept strictly offline) and several, frequently rotating subkeys for encryption purposes. It's not a silver bullet solution (in the sense that a thief would still have access to all your subkeys, meaning he could read all your messages up to the point the keys are stolen, but it mitigates the damage somehow). See here: https://alexcabal.com/creating-the-perfect-gpg-keypair