I figured out a way to start the music to play, but haven't figured out how to get you the shuffle part yet. To do this you need Tasker. It isn't a free app, but it is well worth the money. The things you can do with Tasker are amazing.
Once you download Tasker, create a task within it. Go to the Media actions section and then "Media Control" and select Next from the list. This will automatically start your default music player and issue a "Next" command which will tell the music player to go to the next song and start playing. There is also a Music Play command but it looks like it requires you to pick out a music file to start playing. The "Next" command works quite well.
As for the Shuffle...just leave the music player in shuffle all the time and I think that should do the trick.
After completing and saving the Tasker task, go to the NFC task launcher and select the Tasker task to launch and write it to the tag.