If you're not going to print this very large, you could use a wide angle 14mm / 16-35, etc. and put them in the middle of the frame (to avoid distortion), then crop out the bottom 1/3 to 1/2 of the photo, but given the type of photo (dramatic shot of a special memory), it needs to be high-res for a big print. If distortion is not as much of an issue, you can get close, tilt up and have the arch & railroad converge. Google ultra wide angle wedding photos or something like that for some examples (like this - scroll down to the three 16-35 examples
). That way you still get the full frame.
Another option is to use the TS-E 24 and the shift function to shift, rotate, and shift again for a full panoramic effect. Or simply use shift to correct the verticals and you still have a great full frame shot.
A third option is to stitch, like you say, possibly using the Brenizer effect with a longer lens. A lot depends on how far you can get from the arch - and if that's not the limit, communication with the couple will be an issue.
Just my 2c - there are plenty of ways to shoot this - I'd recommend trying at least 2 to 3 ways and letting the couple pick out their favorite.