It's hard to advise which position you should apply for. Be ready for some soul-searching: where you want to live/work? How job market look like there? What companies are hiring now? What positions? You may be forced to take any position available, if selection is not too wide. Even non-perl job is OK if it pays rent.

My recommendation will be:
(1) Try to work for an employment agency for couple of months. Even for free if you can afford that. You will see how headhunters are working from inside, and it will help you in years to come. Look at it as an investment (of your time). I did it (I developed job matching program for one agency).

Or, (2) try to work for some university around you. Salary is not the best, but you have plenty opportunity to learn. Also, university might be more interested in perl.

(3) If no interesting jobs are around, and you can afford it, work as a volunteer for non-profit agency: build a slick web-site for them. It will allow you to enhance your skills, put something on your resume, and gather good karma in the process. :)

Go to library and read books about job hunting. "What color is your parachute" is a classic (in USA). Excellent book. Find your own.
In any case, post your resume on your web site, and in any relevant job search sites. There are dozens of them. If you want to, I can comment your resume - I read couple hundreds of them...

Do not become lazy. Job search is your full-time job now. Prepare your resume, then customize it for any position you want to apply. Do not send more than 5-10 applications a day, you will not be able to prepare it, (cover letter always has to be customized - highly customized! Plan also time to follow-up.

This is rather stressfull period of your life, especially if it is first time you got fired. Do not take it personally - it is nothing wrong with you. Do not become depressed. I know what I am talking about.

Do a lot of physical excercise. Remember, for last couple of milions of years, stress (danger) always came together with excercise: run away from attacking lion, or attack to defend yourself. Your body craves to go to nearest fitness center to burn all chemicals from your blood, released under stress. If you cannot afford it, run or walk a lot.

Good luck to you!

Update:
dragonchild beat me! Next time, I need to type faster!

I disagree with dragonchild's advice Email bomb EVERYONE.
Email bombing is wrong thing to do, IMHO. Focus your efforts! When you found interesting job, write highly custom cover letter (highlighting you relevant experience, AND change your resume to show how your skills are important/relevant for the job.

In subject of your email, state job position and job code you want to apply to. Make recruiter's job easy. Make sure that your email stands out from the heap of email bombs.

Even better, call hiring manager if you can and send email directly to his address, not to HR dept. Why? HR job is to weed out resumes - to reject as many as they can, and they have minutes to browse it. One wrong keyword, too much experience in wrong area - and you are out. That is why you need to focus you cover letter. And call before emailing - then follow up. Prepare for interview. Read books about it - there are plenty of them.
Do not sound desperate, but find a good reason why you can be enthusiastic and will succeed in the position. Put it in cover letter. They want to hire permanent person.

The more applications for positions, the more you need to work on your application to stand out from the crowd.

pmas
To make errors is human. But to make million errors per second, you need a computer.