1. You are in wrong category
2. Already requested I suppose
3. not supported by PS3 itself
4. can be doable with virtual folder which will create .m3u random playlist when browsed there. I mentioned it here as a tip for developers but I suppose it will be low priority in todo list
Also I suppose that it is not so hard to create virtual subfolders there how deep shuffle can go because at default only files from same folder can be shuffled...