I think someone already brought up the topic about deleting songs from the iPod w/o iTunes. AFAIK it seems impossible.
To do it w/iTunes, plug in the iPod with the computer running, launch iTunes (if it doesn't launch automatically), select the iPod songs you want to remove from the iPod's list of songs, and you're done.
If, however, you have iTunes to automatically update the iPod, I think you will have all the songs removed. (Not to sure, but I thought I read it somewhere.)
Now, I have a question: Sometimes I try to load songs onto my iPod from iTunes and the song does not end up on the iPod. I have to reconvert the mp3s to mp3s once it is plugged in before I can transfer the song to it. And the process is only necessary for a few songs. WTLH?