If you don't have a cell phone, do you really need your contact list with you at all times?
If not, then you have a lot of choices... buy one of those cool little pocket phone books that they sell at office supply stores; create a folder in your filing system called "Contacts" and throw your index cards in there; type the contact info into a text document on your computer, print it out if you really want to store it physically; write it out on loose-leaf paper; whatever...
If it were completely up to me, and the requirements were:
(1) I don't need to carry EVERY contact with me
(2) I sometimes need to carry a contact or two
(3) The contact list MUST be on paper
(4) I need to be able to change addresses/phone numbers without being messy
(5) The system had be cheap, cheap, cheap
then I would do the following: Buy a
small index card box ($2 at Staples). Write contact info on index cards, one card per contact. Store the cards in the box. When I think I need to carry a contact with me, then I would pull the card out of the box and attach it to the back of my hPDA.
Somebody will probably yell at me for suggesting this (you should really get a good handle on the mechanisms of GTD before you introduce new toys), but if you really need to carry ALL of your contacts, and if you can come up with about $100, you might consider getting an
electronic PDA. If you celebrate Christmas, maybe Santa could bring you one?
I've tried to go "paper" in the past, but the convenience of being able to carry all of my contacts, my entire calendar for the next year (actually, the calendar goes out well over 100 years, but who plans that far in advance?!), all of my projects, next actions, someday/maybes, waiting fors, and a good quantity of reference materials all in one tiny package has spoiled me.