So the fisher yates shuffle is a very good choice, why not do this though: Use array shuffle with our seed on 1.9.3+ and only use our own solution on 1.8.7?

P.S. @JonRowe "tame cryptologist", you've seen my beard, I don't think "tame" is the right description :P