I have an S4 mini and I love it.
As Ronski has said, the key is getting a satnav app that stores all its maps.
On a phone, the GPS part is responsible for reporting your position on the map, whilst any data usage is whilst the map is being updated as you move from one area into another.
I dont have a 'dedicated' sat nav app though and not even tried looking for one so Im not sure what is available and therefore cant recommend one.
Before I got the S4 I once used Navfree on my ipad (which has no data connection) when I went to a friends down south. It was ok, but not particularly brilliant as the turn by turn instructions. To be fair, it was in its infancy then, and may be much better now.
These days I use gmaps with the free google Navigation add on. It does allow you to store maps offline but I think there may be a limit as to how much it will allow you to store. Google Navigation is good for a freebie, but I think for it to work effectively it needs a data connection as I always have to turn mine on. It uses hardly any of my data allowance. Possibly about 10-12MB for a 2hr journey there and back.
------
I know you said the phone needs to be data free, but Im not sure if I understand what you meant. Cant you just turn off data if you go abroad?
I have a package which only gives me 250MB of data per month. For the first 3 months vodafone gives 'unlimited' so you can check you are on the right package without fear of any additional charges. I did a massive 120MB and I thought I was trying

I dont do the facebook/instagram nor do I usually mail from my phone. My only data usage is for surfing and using the Navigation app.
I have a nice little app called "Power Toggles" that puts a widget on your home screen giving you full and easy control of what is switched on and off. Press the Data Icon and your phone cant use any data, it's also good for easily turning wifi/bluetooth etc off to save battery. I also put it on dads phone as hes on PAYG so that he cant accidentally use data, yet the option is still there so that he could if he needed.
http://www.appsapk.com/power-toggles/