This was my favorite feature in winamp and itunes. It doesn't seem to exist in many music apps. I couldn't find an android app that does it, and spotify doesn't do it on any system. On desktop, It's possible to script spotify behavior, so with some work I was able to define a global keyboard shortcut to choose a random album and play it. Not perfect, but gets the job done.