You can't really use many of iOS 4's new features on the 3G. About the only thing that Apple decided to give us were app folders. Despite jailbreakers having app backgrounding, wallpapers, and well, pretty much everything and more since iPhone OS 1, 3G owners don't really get anything new. It's kind of lame, really. :/ But yeah, to make a long story short, you'll have to jailbreak if you want to use wallpaper.
Just for reference, the screenshots that I posted were from an iPhone 3G running 3.1.3, jailbroken with Spirit Jailbreak. The theming was done with WinterBoard and the wallpaper was set with BossPaper (with the exception of the default iOS 4 wallpaper, which was set in a WinterBoard theme for ease of application).
Jailbreaking is actually pretty simple if you're at all interested in doing it. When I jailbroke this one, it was literally a minute-long process. I downloaded Spirit Jailbreak (not sure what you'd use for iOS 4 -- I downgraded mine to 3.1.3 before I did mine because 3.1.3 ran much better), plugged the phone in, and hit the big button. It automatically restarted the phone, installed Cydia, and that was pretty much it. The only downside is that you need to wipe the phone if you want to undo everything.