My iTunes collection has been bigger than my iPod for some time, but it's only a 15GB model.
But what I have done is use the option to only sync checked songs, and then unchecked enough songs to give me some free space.... Here is one thing you can do that may not hurt your iPod experience much:
Make a smart playlist that contains XXX (maybe 200 or so) songs that have a play count of zero and the oldest add date. Then apple-click (or it may be option click...I can never remember) to unselect all of them. If you select the "only add checked songs" option, then you can keep using this to get rid of as many songs as you want, from the checklist for syncing, until you are happy with the free space.