I think it's important to separate the two overlapping approaches in your question.
Firstly, Google Sync is essentially a way to use Microsoft Exchange protocols and to setup a Mail / Contact / Calendar profile on an iPhone. The iPhone OS supports this feature, not an iPhone App in the App Store. Google Sync leverages this fundamental capability of the phone by exposing the data (mail, contacts, calendars) via these known protocols. If you want to expose data in this way to your users, setup a Microsoft Exchange server and ask questions on serverfault.
Secondly, there are iPhone apps. iPhone apps sold in the app store are not currently allowed to run in the background. This means you can't emulate functionality like iTunes or Mail where your music plays while you are browsing the web, or mail checking is done while you are playing a game of Mini Squadron. If you want this backgrounding capability, file a bug/enhancement with Apple.. However, you can interact with iPhone contacts (Address Book) via the API.. You can also of course "re-invent the wheel" and expose the data however you like via the internet, and consume that data from a custom iPhone App with the one caveat that users would need to actively launch your application to get to this data and it would not be integrated with the built-in iPhone Calendar, Address Book or Mail applications. Some good examples of that are some of the music community apps that have messaging systems built into them. Presumably that is all being done with web services.
EDIT: It is also worth mentioning that should you go the "iPhone App" route, you should at least consider if push notifications are right for you, and if so how you will handle it.