NOT IMPOSSIBLE to shuffle all your music unless you have an Internet connection. (i.e. It IS possible to shuffle all songs, though it's not exactly intuitive.)
Procedure:
1) Open music app.
2) Open My Music (left button at bottom of screen).
3) Press Songs in middle of screen (in list of Artists, Albums, etc.) You may need to scroll to top of page.
4) Press album cover icon at far left of any song in the list.
5) Press "now playing" bar near bottom of screen (directly above My Music, Playlists, Radio, etc.) at very bottom of screen. Album cover and full transport controls will appear.
6) Press shuffle button at bottom left/center of screen (below horizontal volume bar).
7) Press Next transport button (on right side of Play button). All songs in phone will play in random (shuffled) order.