Впрочем, в последних версиях вроде как собирались убрать джаву, а вместо нее использовать нативные бинарники, скомпилированные под ARM.

Не уверен, что джаву совсем убрали. Но Dalvik VM заменён на ART в 5.0.

Так надо ещё для андроида утилиту написать

ну вот этого я и не знаю. Но вроде многие кричали, что андроид==линукс, не?

Использование сервисов от Google не подходит

Rizado, Попробуйте Owncloud, там можно контакты синхронизировать. Сервер можно свой поднять или сторонний использовать.

Rizado пишет:

К примеру, добавил я в один телефон новый контакт, при подключении к компьютеру он был передан на компьютер, а при подключении второго телефона - на него.

скрипт написать не решение? Можно СУБД привинтить, что-то лёгкое sqlite например. К FireFox уже привинтили.

Так надо ещё для андроида утилиту написать, собрать, загрузить и установить на все устройства. Это с непривычки надолго. Проще использовать что-то существующее. Я знаю, что клиент exchange там есть.  Может есть ещё что-нибудь, что может синхронизоваться с собственным сервером. Это надо не здесь спрашивать, а в форумах по Андроид.

К примеру, добавил я в один телефон новый контакт, при подключении к компьютеру он был передан на компьютер, а при подключении второго телефона - на него.

скрипт написать не решение? Можно СУБД привинтить, что-то лёгкое sqlite например. К FireFox уже привинтили.

s.xbatob, насколько это сложно?

s.xbatob пишет:

Можете развернуть собственный сервер exchange и пользоваться им.

Понятия не имею. Я паранойей не страдаю. И мои коллеги тоже, поэтому мы в отделе при живом корпоративном exchange (который всё время глючил и ломался) купили сервис от google, в который дружно запросились остальные отделы. 
Теперь красота: никакого спама, у каждого единая адресная книга на всех устройствах (у меня их 5: 3 линукса и два андроида), к ней ещё общая для всех, место в облаке, мессенджер и прочие сервисы.

Использование сервисов от Google не подходит - может, я и параноик, но свои контакты чужим людям хранить не доверяю.

Тогда - переписывать вручную, желательно с задёрнутыми шторами и накрывшись одеялом.
Можете развернуть собственный сервер exchange и пользоваться им.

Использование сервисов от Google не подходит - может, я и параноик, но свои контакты чужим людям хранить не доверяю.