Well, here's what. It's very likely that you can get a fat PSP for around 6-7k. If you can get a psp, and install CFW on it, you will not repent it. It majorly pwns every other Portable device out there.
If not, get a creative zen 4 gig + a 2/4 GB SD card. That should cost you ~7k. I own a zen and can tell you that it's sound and video quality are awesome. It is better than the iPod in terms of sound quality and even features. You will not repent this either.
First choice psp, 2nd choice zen. Don't buy the shuffle.
Not having a screen is not a feature! [Despite what some fanboys might tell you!

] In fact the only reason you should buy a shuffle is if you want extreme durability.