The GPS works fine without data connections, just like a dedicated GPS. If you want maps you'll need an app that uses maps stored on the phone, but if you just want position/speed/whatever data there are many good "GPS" apps in the market, often described as "GPS test" but most do far more than the name implies.
I'm in the UK so my experiences (and apps) don't apply directly, but I have full detail OS maps (the definitive UK national maps) using
Viewranger, and for quick GPS features I use
GPS Test Plus.
Viewranger may or may not be of use to you, but I'm sure there are other more US-centric equivalents. GPS Test Plus will of course work equally well anywhere in the world and a free version is also available - same name without the "Plus"
Most places I walk have no phone signal let alone data and I no longer carry a dedicated GPS; the Nexus 4 is not only as good as my Garmin, it's actually significantly better at the job except for battery life. Turn on the GPS on the N4 only when actually needed otherwise it will kill the battery in a matter of hours.