You certainly can't run anything inside the NewtonOS as it's structured very strangely. You'd need either new ROMs or some kind of bootloader that could load linux from the newton os (very unlikely given that the newton os has no design for that). Presumably you'd basically have to redesign quite a bit of Linux, or at the very least least develop drivers for the newton hardware using the arm-uclinux port. The ram upgrade chip would give one a little more to work with. I've heard of it being possible to get Linux down to 8 meg of ram. If you could make an ATA driver you could use CF as noted below or some of those old PCMCIA flash ssds.

Maybe you could netboot something thin clienty?