Android Sat Nav Apps
Android provides different methods for localization. Some of them are network based, some cell based, some GPS based, some mixed (well, that was simplified).

So yes: You could use plain GPS without network. Might take a little longer to get your initial fix, though. (Assisted GPS aka AGPS can speed this up, but requires a network connection.)

And quite logically yes to your second question as well, as far as GPS is concerned. For map data, if it's already downloaded to your device, no data connection is required either. But if you need updates while on the way, or want to be updated about traffic, things are certainly a little different.