In the past I've written that I thought the iPod should have a "Trash Can" or "On-the-go Delete" feature. But through the magic of music synchronization and Smart Playlist you can pretty much create this functionality yourself.
Check out my new instructable "Automatically remove unwanted songs from your iPod." You actually use your iPod to mark which songs should be removed, so you can do it on-the-go. And don't worry this won't delete songs from iTunes, just from your iPod.