Okay, well we've eliminated a couple of things.
One thing I have noticed about the iPod Classic: I suspect that "shuffle" is actually a Playlist, not a real shuffle. The Classic is not as powerful as iTunes or a desktop/computer, so it cannot truely "shuffle songs". I suspect what happens is that every Sync of the Classic with its iTunes Library causes a revised "shuffle playlist" to be put on the iPod and then, when you choose Shuffle play, it actually uses that special hidden "shuffle playlist".
So one trick is to Sync your iPod with iTunes frequently. This would change the "shuffle playlist". Another trick would be to create your own Playlists, either by adding what you want to a Regular Playlist or by creating a Smart Playlist which adds and removes songs by itself.
Smart Playlists: for example, you can create a Smart Playlist (in iTunes) which contains a random selection of all songs, or a random selection of a particular group of songs, provided the song has not been played for a period of time, say six months, or 300 days. Every Sync of the iPod with iTunes would remove any song from that Smart Playlist if it has been played. That same song cannot go back into the Playlist for a period of six months, or whatever you choose.
This way, you can reduce the likelyhood of hearing the same songs too often. This brings me to another point. If you have the same song, on different albums, then it's possible that you are hearing that same song but from both albums.
Try this: in your iTunes Library,
look for and click on the big + button and choose New Smart Playlist..., if you do not have the Sidebar displayed, switch to the Playlists view where you will find it in the bottom left corner,
Set it up to look like this:

It creates a list of songs that have not been played for fifteen weeks. It excludes videos and in my iTunes Library, it has 527 songs in it. If you would like a smaller list than that, click on the Limit to and fill in the number of songs you want.
Having set it up, play some songs from it (in shuffle mode if you wish) and watch how it changes . The song must play through to the end of the track before it is classed as "played". If you like it, let it go onto your iPod. You could set up a few Playlists, each with their own rules. Even if a song appears in two different Smart Playlists, if you have the "last played is not in the last" rule in both lists, then playing the song will eliminate it from both lists. None of this removes songs from the iPod (unless you use Sync selected Playlists...).