onegative,
With such a small number of hosts, you are very likely to hit the same host repeatedly by grabbing a random host.

Why do you feel that you can't keep track of which host was previously called? Have you seen Storable and DBM::Deep?

Another solution, which can be just as problematic as using rand may be to use Time::HiRes. Divide a second into 4 quarters and choose which host to use based on which quarter you are in at runtime.