The other parameter is Pure-Perl implementation of whatever solution seems to be the most plausible.

Oops, I missed that requirement the first time. Pure Perl implementations of ciphers will be much slower and will limit your choices. That said, Crypt::CBC + Crypt::Rijndael_PP or Crypt::Twofish_PP might work for you.

I agree with hardburn that RC4 is tricky to implement correctly and should generally be avoided unless you really know what you're doing and you have a real reason to use that particular cipher.