Rockbox on my very old now Sansa doesn’t have shuffle but random list generation… you pick a song and it will make a shuffled list of the entire library so no repeats till it plays through everything.
ETA of course it isn’t a phone so all it does is play mp3s and it is tiny so having it around is never an issue.
