Note, the question is not CAN you fly without a GPS. I am assuming most people CAN fly without one for any kind of distance, but the question is would you WANT to?
For example, you have a 2 hour leg planned from A to B. You head down to your plane but your primary GPS system (integrated, or standalone) is not working, and your backup or 2nd standalone device (if you have one) is not working either. Worse still, your partner has taken your iPad to work.
Of course you have your charts with you, and suitably drawn lines etc, and you (probably) have paper copies of all en-route airfield plates. The forecasts suggest some low cloud and low visibility, so you anticipate some IMC flying outside controlled airspace, but it would be above MSA, and if you can get enough altitude, you should be able to make use of some VOR radials or cross cut's to keep you on track. Annoyingly your ADF isn't working either. Everything is however within your legal minimums.
Would you go on that 2 hour flight? I don't know if I would. I COULD, but I would'nt be happy about all the extra workload and hassle of dead reckoning etc, and (this might upset some people), I would feel quite uncomfortable without the GPS. That's not to say I totally rely on it - I dont. I always have a backup plan, but it does make navigating easier and flying more enjoyable - mostly. But I would be uncomfortable for the same reason I would'nt want to drive for 2 hours in the car to a place I had not been to without the TomTom and I had to drive using an internet printout or a national car atlas - its hard work (in modern life).
Note, this isn't a real life dilemma for me, just something I woke up this morning thinking and thought it was worth posting.
The short answer is no.
That said, this would also depend on where this flight is supposed to take place. If in the US, I'd say 'yes', as there are enough VORs around to keep you happy. In many parts of Europe or the UK, I'd be much more hesitant.
I would not fly an unfamiliar route without a GPS (preferably two of them)
No. In today's ultracomplex airspace structures GPS is next to unavoidable. Which does not mean to simply fly along the line on it, but it is certainly a much better solution than paper and pencil, particularly if you have the ICAO maps underlaid. That is for VFR. For IFR, without RNAV it does not make any sense in Europe's CFMU world.
The very important bit is redundance and fall back options. I have one installed GPS plus up to 3 hand held ones with me at any one flight, all of which up to date and the route in use loaded. Mostly I use 2 at one time.
So far, I've had handheld ones fail or refuse reception, the inbuilt GNS 430 has been working very well since ever I own that plane.
No
If you bust an airspace it would be considered negligence that you departed without GPS.
However, how realistic is it that you have to do without GPS? Maybe it would be a good navigation exercise but I'd not do it because the risk of busting some airspace is just not worth it.
Having said that, I remember one flight where after 10 minutes I started wondering why the sun was shining in my eyes whereas it should have been behind my aircraft. A subtle spelling error in the GPS waypoint 
BTW, without GPS you don't have to do VOR + dead reckoning. The cheapest and best option still is to ask ATC for a heading. If you give them a few minutes, they will even get you a good wind vector.
If you bust an airspace it would be considered negligence that you departed without GPS.
But mind you, GPS offers no guarantee of not busting airspaces! It only knows about the permanent ones... You must think about NOTAMed ones like militay exercises yourself - been there, done it :-(
But flying without GPS and getting lost is not only negligent, but grossly negligent in my view. And as you say: Be always skeptical. If someting dosen't look right, it usually isn't right. With and without GPS. ATC is there to help you.
If you bust an airspace it would be considered negligence that you departed without GPS.
In the UK, you would get a medal from the CAA whose anti-GPS attitude over many years means that many private pilots still believe GPS is illegal for navigation, illegal for "primary navigation" etc etc etc
They are now paying a big price for this, with hundreds of serious CAS busts (ones that momentarily stop ops at commercial airports) every year.
Only in recent years have they stopped spreading that stuff, and also modernised the IR test syllabus, but it's too late for many PPLs who still believe it, and who fly every 2 years with an instructor whose job is not teaching them about modern methods.
Personally I would do a flight, within UK Class G, if the route could be flown using VOR/DME, and that means being able to find the destination airport that way too.
Otherwise, no GPS = no flight unless it is a trivial flight e.g. 20 miles along the coast.
In the UK, ATC are not going to give you vectors if you are VFR traffic, unless you are in serious trouble or look like you might bust CAS.
Isn't B-RNAV a requirement for IFR flightplans above FL095 anyway?
If I knew it was necessary to fly IMC for more than a fraction of the route I would be on an IFR flightplan, so it's a no. Even without the rnav requirement in practical terms the clearance would be impossible to accept as so many waypoints are not really referenced by VORs any more
"They are now paying a big price for this, with hundreds of serious CAS busts (ones that momentarily stop ops at commercial airports) every year..."
That doesn't tie in with their joint initiative with NATS to produce a cheap and cheerful GPS warning device for ops near CAS: Aware
Infringements have been reduced considerably with its use by hundreds of GA pilots in the UK. It's straightforward, affordable and reliable in my experience. Airspace data is updated every 28 days and charts are also available for France and Germany.
In answer to the thread question - no, unless you enjoy Russian Roulette flying low level in poor conditions.
