You can use a Smart Playlist.
Create a smart playlist (from the File menu), and name it something like "All Songs - No Hoilday" (or whatever you want). Right (or Control) click it and select Edit Smart Playlist.
Check the checkbox for Match all of the following rules. (Make sure you select all, not any).
First rule: Kind - contains - "audio file" (without the quotes)
This rule basically puts everything that is not a video on the smart playlist.
Subsequent rules should exclude things you do not want. So in your case, I would use
Genre - is not - "Podcast" (This excludes podcasts, which would be included.)
Genre - is not - "Holiday"
(Click the plus sign next to the first rule to add a new rule.)
For that "not holiday" rule to work, you need to change the genre of all of your Christmas songs to be the same. It doesn't have to he Holiday; it can be Christmas or whatever you want it to be. Just make the rule exclude every song with that genre name.
If you have placed all of your Christmas songs into one playlist, you should be able to use this rule instead
Playlist - is not - <name of that playlist with Christmas songs>
You can add other rules to exclude songs. For my shuffle, I also exclude the genres Classical and Soundtrack.
Check the checkbox for Live updating. Click OK to save the changes.
Once you are happy with the smart playlist, set it as the Autofill folder. The iPod will then select randomly from a list of all of your songs, minus the ones you want excluded.