Does the iPhone 4 geo-tag photos without a data connection?
Solution 1:
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.