What is the difference between deleting a private key and deleting an address? On Blockchain.info, when deleting private keys from your wallet, it asks if you want to delete only the private key or if you want to delete both the private key and the address. If you choose to delete the address in addition to the private key, does this mean that unless the address is generated again, it doesn't exist anymore? If not, what does it do?
An address can be generated from a private key. But you need to have the private key from the address to be able to spend it's funds. 

So, when deleting the address, it will just be completely removed from your wallet. (Note that there is no such notion of "whether or not an address exists". All addresses exist, but if nobody owns a private key for the address, the balance will be unspeakable.) 

When deleting the private key only, the address will still be in your wallet, but it will be watch-only. This means that you will see the address's balance in your account, but you won't be able to spend the funds unless you enter the private key again. The main reason to do this is for security. If you write the private key down on a piece of paper, f.e., you could delete the private key from your wallet so that a person that hacks into your wallet will not be able to spend the funds.