On the Gnu Privacy Guard Howto I learned how to create a revocation certificate for my public key:

 $ gpg --output revoke.asc --gen-revoke $GPGKEY

Where $GPGKEY is the Key-ID of a certificate in your system.