The iPhone doesn't need any type of data connection for its Nav apps. At least not for the good nav apps. The iPhone doesn't come with a "Nav" app built in. "Maps," the built in app is hardly what I call a nav app.

TomTom's software includes Map data and so do all the other big names and popular apps.

A-GPS doesn't strictly need any data connection. It just uses one, if available, to obtain information from an AGPS server to help acquire satellite signal. You can read about it on Wikipedia, though they do claim that some products need the data connection. I believe they fail to mention any and I've certainly not heard of any current products that fall into that requirement.