I would not be able to fly VFR right across Europe, as I used to do pre-IR, without a GPS.
Of course it is possible but one has to adopt a very conservative approach, because of the high possibility of human error, and the much higher cockpit workload. The price for messing up can be high, and ATC in some places gets awfully nervous as they are themselves only just hanging in there on the English comms.
In practice I would simply not bother to go anywhere except little local jollies along the coast or along well worn routes - much as perhaps 99% of UK GA does.
For me, and for every pilot who flies distances that I know personally, GPS is primary nav, VOR/DME is the backup (concurrent, usually), and if one had to fly on map+compass alone one would sell the plane and chuck it all in. Or buy some Rotax lawn mower and potter along the coast on Sundays. The stakes would be too high for it to be any fun.
Using a GPS as a backup for DR is like driving a Reliant Robin and towing a VW Golf with it, in case the Robin breaks down. It is the worst possible way of doing it.
Using DR as a backup for GPS is much more sensible, but one has to avoid flying in situations where DR is not going to work which is basically anywhere without copious features, or in poor vis.
The best backup for GPS is VOR/DME plus another (handheld) GPS. However, IIRC, DME is not taught in the PPL which is a pity since it is really simple.
I am not an instructor and won't pretend to be
but this subject interests me because I believe the methods being taught are letting people down, badly.