I personally think it's a huge mistake for Firefox to support only ogg. It's a bad time for fragmentation in the push for open video on the web.
It should still be possible to get a rough estimate for when to start playback. Good enough for buffered autoplay.
The best solution would be to simply use system decoders, like Safari does. On Windows, this would be Directshow, on Linux this would be Gstreamer, and on OS X this would be Quicktime. The browser should have ABSOLUTELY NOTHING to do with video and audio decoding.
They do not. For Debian and Ubuntu, it is in Multiverse (non-free) repositories. For Fedora, it in RPM Fusion repository. In other words, there is no distribution that distributes H.264 or AAC, so system decoders would not help at all.
I know! While we're at it, who had the brilliant idea to put image decoders in browsers? I say let QuickTime decode GIFs and PNGs.
Although Chrome supports H.264 video, I believe Chromium does not.
Mozilla already has compile flags that generate binaries other people aren't allowed to distribute -- the logo and trademarks are decidedly non-free, hence IceWeasel.