Index card system
Let me second Frank's recommendation, from the standpoint of someone who used pretty much exactly the system he recommends.
Not sure if anyone will remember, but this idea was actually a system that sold (predominantly through airline magazines) about 10 years ago. You'd buy portfolios or inserts for your preferred binder. The inserts/portfolios had slots for notecards on which you'd list projects and next actions. I used it for probably 2 years before migrating to Covey. I migrated b/c 1) Covey was very in-vogue in my organization, 2) I liked the daily record of events feature, 3) at the time, the inserts only came in 8.5 x 11 inch format, and that made schlepping the binder around a bit much for me, and 4) standard index cards were a bit long for the slots, so the options were ordering huge quantities from the supplier or trimming your own index cards; since I hate the idea of not being able to restock at a moment's notice, I opted for the index card route and I got tired of trimming by hand. I'm not sure whether the system is sold any more; haven't seen ads for them in years.
In retrospect, the system worked pretty well, and as you've noted, it's easily adapted to GTD. And while the binders made overviewing easy (the project names "peeped" out of the slots so you could in effect do the horizontal landscape scan of your project list in about 30 seconds, and then pull the card for the one you wanted for vertical scanning), they wouldn't be even close to necessary. As I think back on using the system, I'm amazed how useful it would be with GTD, and although I find my Palm an invaluable aid, if I had to be somewhere without it, this might *very* well be how I'd adapt...
Bottom line: Frank's recommendation is both do-able and usable. I'd give it a try.
HTH,
Bryan