Even easier on the iPod Touch.
Note that there are two separate places where you can turn on Shuffle Songs*, but they work differently from one another.
To do what you want; i.e. start a song of your choice playing - and then for it to shuffle from the end of that song, do not use the Shuffle button at the top of the Songs menu.
Instead:
- on the Songs menu, choose the song you want and start it playing
- you will see the song you've chosen at the bottom of the screen, as indicated by the Now Playing ribbon
- tap the Now Playing ribbon to bring up the full-size Now Playing screen
- drag the Now Playing screen upwards, to reveal additional controls below the transport controls (Shuffle and Repeat)
- Tap the Shuffle button that you will see on the left hand side of the Now Playing screen, so that the button turns red:

In the screenshot above, the iPod is in Shuffle mode (which we know because the Shuffle button is in red with white text. Your Shuffle button will be in light grey with red text (like the Repeat button, which is currently off). Tap the Shuffle button to turn on Shuffle and the button turns red. The song you've chosen will play the the end and then the iPod will begin shuffle play.
While you're here, here's a couple of tips. First, a word about the Repeat button. Similarly to your iPod Classic, Repeat cycles between:
Off - once the current list of songs finishes, the player will stop
Repeat - once the current list finishes, the player will repeat the same list
Repeat 1 - the player will play the same song over and over, until you tap Next button or stop the player.
Off - (again)
In the screenshot below, notice the small 1 in the Repeat arrows button. This indicates that the iPod is in Repeat 1 mode, not simply Repeat:

Second tip: drag the Now Playing screen up even further to reveal the Up Next list. If you are in Shuffle mode, the list is already in the shuffled order that it will be using. (There are various things you can do with the Up Next list too, but I'll leave at that for now. That's for another day.)
* Edited by author after initial posting, for clarity