Create MarkContactsWithNoMessages

First you must create a new Google Contacts group called "ToBeDeleted".

Then make a full backup of your contacts aka Export Contacts.

Then run this script, may take a few times, depending on number of contacts you have.

Basically what this does, is loop through all your contacts, see how many messages they have in your Mailbox. 

If they have no messages, then it adds them to the new contact group, "ToBeDeleted".

Then what you can do, is look through that contact group, and remove those you wish to keep or save.

Then delete the rest, this gives you a safe way, to delete contacts that you never sent/received any messages from.