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.