In a few weeks, I will have the iPhone 4. I won't take data with SMS-call hours. But I love taking pictures wherever I go, and the geo-tagging feature is a great thing.
Does the iPhone 4 geo-tag pictures usefully even without data?
Yes; The Geo tags are written into the images via the native Location Services within the phone, primarily via the GPS chip the phone contains.
Since the information written is merely latitude/longitude, you do not need to have a data connection in order for that information to be determined and added.
The need for a data connection in tandem with photos is the ability to place them on a map, when using iPhoto for example.