Amperfy for the Iphone randomizes the shuffle.

I just looked at the code and it's apparently using the Fisher-Yates shuffle with a call to arc4random each pass. It's literally eight lines of Swift!

I've never suggested this before, but if the Android app store has truly been as bad as you claim for as long as you claim, you should seriously consider buying an Iphone to solve your problem.