Hi Wirux, welcome to the community!
Could you please provide the output of: ./certbot-auto --version?
The two-line change suggested here: Certbot has problem setting up the virtual environment, should also work for you. The changes are applied directly within ./certbot-auto.
As a check, please provide the output of: grep virtualenv ./certbot-auto.