Is it possible to sort all Gmail contacts by contact frequency, either directly from Gmail or using a external tool/service? How?
Not in GMail. The only free consumer service with a similar function is Gist. It allows you to sort contacts by "Importance" (overall frequency & depth of conversations) and by communications sent/received to/from a contact. However, it scans only the last 30 days of communication history for new accounts. Everything else is expensive enterprise customer relationship management software.
You can also have a try at xobni.
It had this functionality on Outlook, I do think it will work for Gmail too. And it adds a lot of funny (or useful) features.