The Perl Cookbook, recipe 15.11, discusses how to best use the Term::ReadLine. It mentions looking at the Term::ReadLine::Gnu for other options. I've never used it, but I bet it'll help you out.

Specifically read through this part about Custom Completion.

I'd be glad to hear if it works for you...