No need for GPS at all. Have been doing RNAV departures and arrivals for quite some time now in classic 737s. They can work quite nicely even down to RNP 0.5 if you have sufficient DME coverage for rapid updating. If ANP becomes worse than RNP (for example with NAV radios switched to manual) the plane tells you in big amber letters right across the Navigation Display that you're on your own now.