I was considering some sort of size limited tied hash, and then shifting an element off, but was looking at what others might suggest.

Sounds like a good solution to me. CPAN has some modules already, but this is probably the kind of thing I'd do myself.