Sorry to hear about your situation. I guess it'd not affect if you land without proof of employment. As I said, my friend asked the question during his landing but they didn't emphasize that a person under closed work permit should take his/her recent pay stub or any other letter from the employer.
Also, If a find a job what should I do now, do I need another work permit support letter from PNP? - If your provincial nomination date is expired, I highly doubt that PNP would give you a new support letter. But you can call them and ask casually.
Does the new employer have to fill out IMM 5802 LMIA Exempt form and pay the $230 fee? - Yes, provided you're LMIA exempt. And you can only be LMIA exempt if you already have valid provincial nomination or you're on a Post Graduation Work Permit.
Even if the employer does that it will take another 4 months for me to get the new work permit. Is there anyway I can start working again and get the new work permit immediately? - No. Unfortunately the processing time is long and there is no shortcut to it.
My advise - prepare for IELTS again as getting the highest marks in IELTS makes a huge difference.
If you don't believe, try putting the highest and lowest scores in your IELTS in CIC's link - http://www.cic.gc.ca/english/immigrate/skilled/crs-tool.asp
You will see the results for yourself. If you are single, have atleast 2yrs of Canadian experience with a Canadian Degree or WES certified degree, you can easily get score above 450 points. Then apply for Express Entry.
Best wishes.