Letterboxing is very much the precursor to geocaching, although it's available in relatively limited places compared to the former. Dartmoor is where it was invented, and is thus the most popular place - you can easily find some boxes just by looking under "suspicious" rocks. I believe it's also available elsewhere in some areas in the US, though I'm not sure where.
You can of course still use a GPS, though it's entirely possible to find boxes without. You're usually given a grid reference and a number of bearings to the correct point - you have to navigate to that point and then search around for the box. It takes more time, especially initially - since you have to stop and gauge bearings pretty accurately. However, I personally find it more fun since the effort and therefore reward is greater!