You say "patent licensing" as if it was just signing a legal agreement. Their license requires significant royalties to be paid and which we must all pay.
And more importantly, if a patented piece of software requires payment of any royalties whatsoever, it instantly violates the "no further encumbrances" section of the GPL. If that software derives from or includes any GPL components, poof, it instantly loses the right to be distributed.
So if you want video on a Free Software system at the moment you must choose one of the following four options:
1. Abandon the GPL and any dreams of having a fully free desktop system. Just bow, accept that The Market Has Spoken And Freedom Is Dead.
2. Abandon the USA as a market for a regime which doesn't recognise software patents, and hope international treaties don't impose US-like silliness on the world.
3. Abandon the law. Resign yourself to breaking the law and either living like a fugitive, accepting the penalties or trying to make a test case out of your lawsuit.
4. Abandon the known patent-tainted H.264 for a (hopefully) non-patented alternative like WebM, or one for which the patent imposes non GPL-violating encumbrances.
(or, as a temporary solution, sequester the video-rendering component in third-party "dirty" code, like a Flash plugin, written using no GPL libraries, while you initiate a proper project to replace it).
Or you could develop a superior codec, get hardware manufacturers to support it in hardware, and then enjoy your ideological purity. Of course, that would take a significant amount of time and effort and a full time team of people working on it, people who would require pay. Plus you'd need a war chest to fight off patent trolls, etc. Probably need to market it too since you would want people to come to your movie store and your video streaming site.