Web browsers (and HTTP in general) have had content negotiation support for ages. I'd imagine it could be used here as well.
That said, your suggestion really just pushes the patent problem on to content producers. To make sure the video would be viewable by the maximum audience, producers would need to provide both formats. Now they've got to deal with patents on the H.264 encoders.