There were no alternatives to GIF; no one did what GIF did.  It seems to me that if every major browser supports Theora and Vorbis in html5 video we will have come out ahead of where we were with GIF:  Licensing policies won't change because if they did everyone could switch to Theora.  The only problem, then, is getting Theora support in Internet Explorer (it's already in FF, Opera, and WebKit).