If you delete a song from iTunes, the next time you sync your iPod, it gets deleted. I know in the preferences for the iPod, you can set to manually sync the iPod or something. That more or less means you drag what songs you want to your iPod. I'm not sure if this will help you.
External hard drives are pretty cheap. I'd just pick one up.