You could try the Venezuela Civil Registration, 1873-2003 registers available on FamilySearch.org. They contain Births, marriages, deaths, indexes and other records created by civil registration offices in Venezuela.
If that doesn't work then definitely contact the local city hall. According to the US Embassy in caracas:
The Civil Code states that a civil marriage can only be contracted
between a woman and a man, and it must be performed in the
municipality where either the man or the woman resides.
So the record should be in the Municipality that the marriage took place.
You could also try contacting the Embassy of Venezuela in the United States of America. They might be able to offer more help in English rather than Spanish and probably have experience locating marriage records. Or contact whichever Embassy of Venezuela is applicable for your country of residence in Europe.