Here's one way (on a mac):
1. Set up two playlists. Playlist A has 1000 songs or so. Playlist B is empty.
2. Select Playlist A, and make sure the "Up Next" queue is empty. (You can click "Show Up Next" from the View menu to see it).
3. Hold down the option key while clicking the Shuffle icon near the top of the screen. This will add all 1000 songs from Playlist A onto the "Up Next" queue.
4. Highlight all of the songs in the Up Next queue. (i.e., select the first song, scroll to the bottom of the Up Next list, and shift-click the bottom song)
5. Control-click that highlighted list, select "Add to Playlist", and choose Playlist B.
Playlist B now should have a randomized list of the songs from Playlist A, that you can synch to an iPod or whatever.
Another tip: To get podcasts to get mixed in with all my other audio files, I always change their Media Kind to Music and uncheck the "Remember playback position" and "Skip with shuffling" boxes after downloading. (You can see those via "Show Info")