Today, Apple released the first iPod Updater which brings new functionality to all iPod models, including the very first one with mechanic wheel! Now, all iPods feature almost the same functionality on the software level, for instance the ‘Shuffle Songs’ command in the main menu. If the menu item doesn’t show up after updating the iPod’s firmware, reset the main menu settings (Settings > Main Menu > Reset Main Menu > Reset).
It looks like the Apple iPod Firmware online petition worked after all 🙂