The iPod Linux Video Player now supports the iPod nano. Sure, the videos aren't even up to the paltry 320x240 h.264 quality that Lost episodes come in, as this little trick can only play specially encoded AVI files, but it does have both video and audio working on the nano.
So, if you impressed your friends last week by rocking out Doom on your nano, then you already have Linux installed on your iPod and you're good to go and wow them again with the video player. If not, then you're going to have to take the few extra steps of installing Linux and possibly voiding your nano's warranty. If you give it a shot, let us know how it looks on that itsy bitsy screen.