After Googling for the answer for the billionth time, I came across Bugzilla's recommendation: Compile your own perl in your home directory and don't worry about it.
This works like a charm! I had to tweak my CPAN and CPANPLUS config files a little, but I think that was just because I was trying to do things the hard way earlier. It takes up more space, but now at least I get to play with Catalyst in shared hosting environments without any problems at all. (Wow. Catalyst isn't in the top three when googling for it? Kind of odd for an OMGRADWEBTWOPOINTOHFRAMEWORK.)