The most likely early example of a movable bridge (assuming you allow pontoon bridges) allowing a ship to pass either under or through is Xerxes' pontoon bridge from 480 BC and is cited by Herodotus. Between this and the old London bridge completed in 1209, there is little that one can confidently say qualifies.
With Xerxes' Pontoon Bridges (480 BC) the bridge builders left
a narrow opening to sail through in the line of fifty-oared ships and
triremes, that so whoever wanted to could sail by small craft to the
Pontus or out of it.
Unfortunately, Herodotus doesn't provide much detail on this. There were, apparently, three openings but how they were 'constructed' is unclear.
This 2005 University of South Africa master's thesis, From the Scamander to Syracuse: Studies in Ancient Logistics (pdf), proposes that ships passed under the bridge thus:
All types of sailing ships of the time had masts which could be easily
unstepped. A passing cargo ship would have needed headroom of two
metres at the most with its mast unstepped in order to pass under the
bridge cables. With that in mind, it is suggested that the simplest
solution to the problem would have been for four triremes on each side
of each “gap”, that is, 24 altogether, to have been modified by
fitting baulks about twenty metres long lengthwise, raised by 25, 50,
and 75 centimetres and one metre successively above the deck level, to
lift the road over the cables by a gentle slope to about 2 metres
above water level which would have been sufficient for a merchant ship
to pass underneath.
On the other hand, Otis Ellis Hovey's Movable Bridges (1926) states that parts of the pontoon could be pulled aside to allow ships through:
at three places boats were lashed together and arranged so that they
could be swung aside to allow ships to pass through the openings.
These appear to have been genuine pontoon draw spans.
With the Romans favouring fixed arch bridges and with evidence from China inconclusive, Hovey then adds
...it is difficult to trace the use of movable structures for several
centuries after the beginning of the Christian era.
This brings us to Old London Bridge (cited by the OP and also by Dijkgraaf in a comment). Started by Henry II in 1176 and completed in 1209 during the reign of his youngest son John, it survived 600 years; a
particular feature of Old London Bridge was the drawbridge which was
sited near the middle of the bridge.
"Detail from a 1632 oil painting, View of London Bridge, by Claude de Jongh." Note the movable (drawbridge) centre section. Source: Londonist
This allowed tall ships to pass through and the bridge was also notable for the houses and shops on it, though it was not unique in this respect. Interestingly,
Old London Bridge reached its pinnacle of fame in the sixteenth and
seventeenth centuries. Tourists came from all over Europe to admire
what was considered a wonder of the world.
Perhaps the centre drawbridge was partly a reason the bridge being 'a wonder of the world'; there is certainly scant evidence for other bridges across rivers with a movable section for ships to pass through which dated from the high medieval period.
Very borderline cases
Hovey's Movable Bridges has a section on Ancient Movable Bridges. He covers ancient Egypt, but makes no mention of ships being able to pass under and there does not appear to be any evidence that such bridges existed. At most (citing Edward H. Knight),
the Egyptians built no permanent bridges across the Nile, but were
familiar with framing trestle work, and with pontoon draw bridges.
For the 6th century BC Chaldean bridge mentioned here, there is no evidence that it was movable; it may have had a removable section to allow ships to pass, but we can't say for certain.
Hovey also cites Herodotus on Queen Nitocris of Babylon's bridge (circa. 460 BC) across the Euphrates which had "movable platforms". The purpose of these, according to Herodotus, was to prevent robbers crossing the bridge at night.
Finally, Wikipedia's Bascule Bridges article says these date back to ancient times but provides no sources, and nor is there any mention of ships passing through or under.