My phone can use GPS (5 meters accuracy), and if it's off it'll use cell tower triangulation (500~1000 meters or so accuracy, or if wifi is on and there are access points around it'll use WPS (almost as good as GPS in populated area with a lot of WIFI signals).

As far as map goes, if you use an ONLINE map service such as google map obviously it won't work when there is no signal (though you can pre cache area in gmap if you choose). You can download navigation apps or topo map apps that will store them locally, I have sygic navigation installed for back up. (though you do need a couple of GB of free space for the maps, 4.7 GB in my case)