To get a GPS signal, you need to be outside with a clear view of the sky. It can take 20 minutes or more for it to lock on so be patient. You also need to have location services set to "on", which you said is set that way.
With no data plan, the device cannot download the GPS ephemeris tables which tell it which satellites are where. It also helps to know approximately where you are on either BBMaps or Google Maps to make a lock on quicker. Google maps should be able to use cell tower triangulation to locate you within a mile or so.