eBuddy appears to be the first free multi-protocol IM client for iPhone 3.0 with push notifications. The client supports MSN messenger, Yahoo! messenger, AIM, GTalk, Facebook and ICQ. I’ve confirmed it to work with GTalk on 3G/GPRS & WiFi… but there is one catch, it will only work for a maximum of 30mins after you close the application.
Do note that the application signs you out immediately by default, hence rendering the push notifications useless, so be sure to set the app to only sign you out after 30mins (max).
FYI – Appadvise.com are maintaining a list of all apps that support push notifications – check it out here