You are asking two questions, I believe. One is how to remove songs from the iPod without doing a Restore (erasing the iPod).
The other seems completely unrelated to the iPod. I think you have a situation where you have manually moved your iTunes Media folder (outside of iTunes), so iTunes no longer knows where your song files are located. Therefore, in your iTunes library (not your iPod), the songs are greyed out and cannot be played.
Does that sound right?
If so, do you still have your old computer, where your iTunes library worked properly?