How do I restore a contact I deleted on my Android phone, but not in GMail contacts?
Method 1
Stop syncing with Google account, check that all Google contacts are gone, set up sync again. 

Method 2
Remove the Google account, add it again.

(You can do both in Accounts &amp; Sync from phone Settings.)