You don't have to "delete" songs, but instead simply remove some from the iPod so that there is enough room to add the new songs. If you have the option to Sync only ticked sings and videos turned on (checked) in iTunes, then yes, unticking them will cause them to be removed from the iPod, but keep them in your iTunes Library, ready to go back on when you want them.
An option that you might wish to consider is using Smart Playlists to mange your iPod. By creating Smart Playlists, in iTunes, that automatically remove and add songs to your iPod (acording to the rules you choose) it is possible to remove songs from the iPod that you can live without for a while and add new music in its place.
If that sounds like something you would like to try, but you need help in creating Smart Playlists, plesae ask.
KelcyBl wrote:
Is there a way to get more memory?
No. (Or rather, only by buying a larger capacity iPod.)