You don't have to do anything fancy, I don't think. Initialise your RNG with the seed that you have stored, shuffle the list, and then rotate the list to get to the 'first song'. Every RNG seed will give a correct result.

If you shuffle using eg. Durstenfeld/Knuth shuffle, which is O(n), then you can make a note of the 'first song's position' and do the rotation at the end of shuffling straight to the first song, in a single pass.

You'll still get a repeatable ordering if songs are added or removed from the playlist - the order will be different, of course - and it takes a lot less storage to write down the seed and the ID of the 'first song', which might matter if you're using a crappy old music player with very limited storage space.