As a long time Evolution user, I had the same problem when I got my first Android phone about 18 months ago. The solution I came up with was to first "sync" Evolution to Google Contacts. Then I added my Evolution contacts to the Google Contacts in Evolution. That gave me one unified location for all my contacts. (By the time I did this I had some email addresses in Gmail that weren't in Evolution, and a 10-year-long list of contacts in Evolution that weren't on Google's servers. My Blackberry synced the old fashioned way: A docking cradle and serial jack.)
That said, as you've probably noticed, Google's Contacts are somewhat limited. While you can break your contacts up into "groups" (tags), and even assign one contact to multiple "groups", what you can't do is filter by multiple groups. Say, for example, that some of your contacts are sales prospects. Their core "group" is, of course, "prospects". But being a smart sales person you also use the tags "hot", "warm", and "cold". You can assign your prospect to both "prospects" and "warm", but what you can't do is filter by both "prospects" and "warm" to see a list of contacts that exists only in both "groups". This is a major failing with Google Contacts and, in my opinion, is rather weird since organizing information via tags has become, almost universally, the preferred method.
You'll also notice that all of your Google Contacts now exist in Evolution under "Google", but the "groups" that you created in Google do not carry over to Evolution. So they're there; you can get a all your contacts in Evolution, but they're an unsortable lumped up mess. This seems to be a failing on Novell's part, since on my phone I use DW Contacts and all the "groups" are there, and I can even do "group" based associations. The only work around I've come up with is to make sure that those contacts I may wish to use via Evolution exists both "On This Computer" and on "Google", so that I don't wade through the Google mess more than absolutely necessary to find the contact I want.
Best Answer
Export your contacts
My Contactscontacts.vcfin a text editor. Ideally Notepad++ or Notepad. Not Word as it'll probably make unwanted changes to the file.BDAY:1900-01-01and replace withBDAY:Delete your existing contacts
My contactsMy Contactsis empty.Import your updated contacts
Browseand select your modified vcf fileImportto import the modified contacts into Google.Bear in mind that you will lose all contact pictures. I personally use Sync.ME (available for Android and iOS) after the last desktop application I had that did this stopped working.