It seems that the optimal solution would be to obtain a modern device with removable media. I wish Apple hadn't decided to make storage size part of their pricing model, and offered a card slot.
My Motorola Droid phone has a micro SD slot, with a max size of 64 GB. It would be a lot more convenient to carry a phone and 6 memory cards than a phone and an iPod Classic.