You certainly can do this and I do it everyday. I also rearrange some tracks while playing to better match my 'random' mode.
Select the Playlist (don't hit Shuffle All) and just scroll to the track you want to start with and click on it. It then builds a Up Next list from the Playlist (then just make sure the shuffle icon is toggled on). You can then also rearrange the tracks if you don't like the order they are in.