IMO the easiest way to get wallpaper on my iPhone is via email. I send myself a message via Gmail w/the wallpaper images attached, access the message through the iPhone's mail client, save the images to my phone, then set from either Settings | Wallpaper, or directly from the camera roll.
I believe the 3GS has the ability to get updates OTA, though bigger updates like 3.0, 3.0.1, 3.1, etc. are all done via iTunes. I'm hoping the carrier file update for AT&T customers later this month to provide MMS will be OTA...
HTH