It seems that you should be able to seed using the integer representation of the host's IP address, or an integer representation of the characters from the hostname, and end up with stable results.
An aside: I was just reading this last night, for no good reason: Fisher Yates Shuffle: Pseudoraondom Generators: Problems involving state space, seeding, and usage. I'm not convinced that Perl's randomness generator is free from this issue, which would make your Fisher Yates shuffle (as well as the one included with List::Util suspect.
Hopefully someone can settle this concern. But reading Algorithm::Numerical::Shuffle's POD confirms that implementations using rand may have a flaw.