La gestione dei contatti di Android è veramente pessima (anche quella di Nokia non scherzava, comunque), alla fine GMail è la soluzione più pratica, anche se è un ripiego. Comunque alcune applicazioni di sync da PC, come quella di LG per esempio, vogliono una connessione attiva (anche WiFi) per sincronizzare i dati (?).
Per il momento non mi sembra esistano applicazioni serie di sync con Outlook (per dirne uno) per gestire contatti e task.