I went through the same problem when I first got my phone. The Google sync didn't do my contacts. I searched for a while and found this excellent program called Companion Link. It does exactly what you need and syncs back and forth between your phone and pc Outlook.
It does still use Google as the middle point so you do need to have that set up but you probably already have that account when you set up your phone.