I accidentally deleted all of my Gmail contacts with my Android phone…

…but this is why I use Gmail instead of, say, Hmail or Ymail. I restored all 1,000+ of my contacts by logging into Gmail on a PC and doing the following:

1. Click Contacts.
2. From the More actions drop-down menu, choose Restore contacts.
3. Choose the time you’d like to revert your contacts list to (e.g. 10 minutes ago, one hour ago, one week ago, etc). We suggest that you also make a note of the time that you restore your contacts, in case you’d like to return to where you started.
4. Click Restore. You’ll see a confirmation at the top of the screen when the rollback is complete.

You can perform a restore from up to 30 days ago.

This info plus more can be found on the relevant Google support page.