The main question isn't a language question but is a design question: how robust a solution are you trying to create? If your only record of queued requests is a hashtable in memory being shared between threads, any disruptions in that process (tripping over a power cord, perl executable segfaulting etc) will cause a loss of your queued requests.
I'd start with trying to use apache/mod_perl as my platform to avoid reinventing a lot of wheels, but to write this kind of throttling proxy server in a bombproof manner is not a trivial exercise.