Force Vassalization is generally the way to go, temporary switching their culture group (works just as well as faith).
However, since they're already under the thumb of the Byzantine Empire, all you have to do is to conquer the title as a claimant (getting a claim through marriage shouldn't be hard) and you're all set. Afterwards you can destroy the title and even release the vassals you're not interested in.
As for dealing with Venice, I recall pressing the claim of a bastard of one of the five families of a merchant republic once. I can't remember how he acquired the claim (as they are not given to the rulers children as in feudal realms) but possibly his father was an ousted doge who therefor received a strong claim. Anyway, as the bastard had a different dynasty and there already were five patrician families, he didn't become a patrician. This meant that the government of the merchant republic became that of an ordinary republic, but with five patrician families. I don't know how the succession worked (whether if it was patrician elective or simply open elective) but one of the five patricians became doge and with that the republic became a merchant republic again. A similar scenario can play out if you chose a start date where one of the republics is ruled by a non patrician, Venice in the Alexiad for instance. In those cases the republic's succession is that of patrician elective.
Now if the game still functions as described above, you could theoretically invite a claimant for Venice when one pops up, marry him matrilineally to one of you're kinswomen. If his claim is uninheritable, press it and then white peace before waiting for him to die. Lastly, press the claim for one of your claimant kinsmen. As kinsmen (unlike ordinary courtiers) become your vassals once you press their claims, you should hopefully end up with a vassal ordinary republic with five patrician vassal, which will then switch back to a merchant republic after succession. It's up to you if it's worth the headache. And, of course, I offer no guarantees that it actually works.
EDIT: While writing this I got excited to try it out. I started as Barbarossa in 1187 and gave prince Otto a claim on Venice (console commands, obviously). Unfortunately, he became feudal once the war was won (even if he only held the titles Kingdom of Venice, County of Venetzia with the City of Venetzia as capital holding; i.e. no held castles). My previous experience were probably before "governments" had been introduced and feudal, republic and theocracies where distinguished by the type of capital holding (barony, city, temple).
However, the good news is that I was able to use Force Vassalization CB against Venice as the HRE emperor. So a single sea zone probably counts as sharing a border.
