In the old version of the music app you could shuffle all songs when songs were selected:

This feature seems to be absent in iOS 8.4 and the new music app:

What are the options for shuffling all my songs in the new version of the music app under iOS 8.4?

Solution 1:

• In the My Music tab under the Recently Added album artwork is a title which by default reads Artists it is a pink drop down menu.
• Select Songs from the list.
• Select any song to start playback.
• Enable shuffle mode, disable repeat.

Solution 2:

The above solutions didn't work for me. What worked for me was after starting a song, I tapped the bottom bar that shows what's playing. Upon tapping, a window with the album cover appears along with the player controls, including the shuffle and repeat buttons.