Some time ago I writed LWP::UserAgent subclass, which main purpose is to automate proxy rotation for each request. It is not finished, not well tested and not documented yet, but you can try:
LWP::UserAgent::Proxified
Simpliest variant of usage:
use LWP::UserAgent::Proxified;
my $ua = LWP::UserAgent::Proxified->new(
proxylist => [
['http', 'https'] => 'http://10.0.0.1:1080',
['http', 'https'] => 'http://10.0.0.2:1080'
],
proxyrand => 1, # choose random proxy for each request
# other lwp options goes here
);