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.
No, it has not been implemented (that is, there's no GUI for it, but an API).
I believe the Shared external contacts feature was added to properly support syncing with Exchange servers, which have this feature. As such, you can only add shared contacts from your synced Exchange server, or, as you say, by using a third-party application that you can find in the Google Apps marketplace.
Best Answer
"Other Contacts" consists of:
You can keep it from auto-populating by changing that Gmail setting. Not much you can do about what it does with G+ Circles. And make sure all of your contacts have labels.