I'm pretty sure the paid version of PowerAmp for Android will do what you want, with or without explicitly creating a playlist.

I have many thousands of mp3s on my phone in nested folders. PowerAmp has a "shuffle all" mode that handles them just fine, as well as other shuffle modes. I've never noticed it repeating a track before I do something to interrupt the shuffle.

Earlier versions (>~ 5 years ago) seemed to have trouble indexing over a few thousand tracks across the phone as a whole, but AFAIK that's been fixed for awhile now.