No problem. There is this company in Kiew called RESURSY-DOKUMENT . Adress: Klowsjkyj uzwiz 13, tel. 280 13 32
You can write a power of the attorney (informal, does not have to be notarized or anything else) to any friends you have there, they just bring it to the office with their passport and 93 griwnjas for police certificate. It is ready in 3 days. R u ukrainian? I have an example of power of attorney, I can send it to your e-mail if you want.
Another thing to share. My friend sent the documents via DHL from Kiew and it took me almost a month to get it. Canadian Customs seized it (randomly) and as I was told they have write to do their own investigation (where the document is authentic) for 3 weeks. After DHL messed the delivery up, so I would recommend to send it via regular mail. Anyway just my sad experience.
Oh, yeah the other way to get a police certificate is through Consulate General of Ukraine. This can take up to 6 months.