While I agree that cable stay bridges (be they symmetric or asymmetric) are beautiful, they look very modern and would clash when set beside the gothic architecture of the parliament buildings.
If you were wanting to avoid building a truss bridge, a suspension, tied-arch or maybe even a cantilever bridge would be more appropriate choices IMHO. My leaning would be towards the latter two as you could tie in truss elements to pay homage to the original design. See
7 Iconic Bridge Designs (& Their Utilities) for descriptions of those types of bridges.
Almost any type of bridge can be made to look either beautiful or ugly (though its hard to dress up a beam bridge). As I said before, the Alexandra bridge is a bit limited by its lack of elevation in that the features need to be largely above the deck.
Looking closer at the design, it actually has multiple bridge types in one:
Drawing Showing Entire Bridge
Source: Waddell, J.A.L., Bridge Engineering Volume 1, 1916. Digitized By Internet Archive.
The southern portion is a cantilevered design balancing on two piers. The next two spans are trusses (one arched and one not) and the northern approach is a simple beam bridge. For its replacement, I would lean towards one cohesive design.
EDIT: There is also a short beam bridge on the northern approach.