I just got an iPhone 4 and I'm trying to figure out how to get my contacts on it. I don't have an exchange account, which seems to be the only Google Sync option.
Open Address Book on your computer and go to Preferences > Accounts. Turn on Synchronise with Google and enter your Google account details. Your contacts will come through to Address Book and will then synch to your phone in iTunes.