Hi, This is driving me mad!
Last year the info was that officially the Embassy will contact the Venezuelan authorities and Police certificate will not be necessary.
Today because your question, I'd realized that they change the procedure once again, maybe since they closed the caracas VO.
I'm sorry but if you speaks spanish, I'd recommend you to contact Ms. Laura Collauto, she is been a responsable person here you go the link to her website.
http://www.tramitesenvenezuela.com/site/index.php?option=com_contact&view=contact&id=1&Itemid=194
Do I need to provide a police certificate when applying for permanent residence?
Yes, all applicants aged 18 or older must provide a police certificate.
How do I obtain one?
Police certificate should be requested by writing a letter addressed to the “Viceministro de Seguridad Jurídica del Ministerio del Interior y Justicia” indicating the:
date,
reason for request,
photocopy of your Identity Card, and
applicable fees.
Since police certificates can only be issued from a public authority, you must mention that it is requested by the Canadian Embassy.