The new music app has made strides in terms of its shuffling capabilities with the new iOS 9 beta version that was released this last week. However, songs marked in iTunes as skip when shuffling still get mixed in the shuffle all feature. Who knows if it is something that Apple will address anytime soon. My guess is that it's not exactly high on their priority list.
But I did manage to find a work around from another thread. It will require a little tweaking in your music library, but you can create a self updating smart playlist and name it something like Shuffle. As a rule you can create something like Comments -- is not -- No Shuffle. At this point it would probably pull in every song from your library. If you then went through the info for the individual tracks and added a comment that said No Shuffle for the songs you had marked as skip when shuffling, those tracks would automatically be removed from your smart playlist. So now when you shuffle that playlist, it plays only that which is in your library that you want to hear. Want a song back in that playlist? Simply just delete the comment.
As you get more comfortable with building smart playlists, you can get creative in the way you set them up. But this way essentially creates the same effect as clicking the Shuffle All option and having it skip the songs marked as skip when shuffling. And may be your best option at this point. Hope this helps.