Why wouldn't something in the cloud work for you?
I personally have a Google Apps account that I connected to my iPhone as an Exchange account, and it syncs my Contacts and Calendars plenty well, and gives me my mail at the same time.
I presume a regular Gmail account will serve the same purpose.