Is there a way to add an iPhone contact and have it sync to an Exchange server without having to cable sync through iTunes?
Set up your iPhone with your Exchange account and it'll sync over the air.
Settings -> Mail, Contacts... -> Add Account
Then choose Microsoft Exchange.
It'll configure email, contacts, and calendars, although you can choose to turn off email and calendars if you want to.
Then, in Contacts, select your Exchange contacts, and add new.