And what of Linux, and its variants like Android or MeeGo?

Yes, Linux is a bit of a problem. In case of Android and MeeGo, the distributor or the manufacturer can deal with licensing issues and ship the device with a licensed codec.

The real problem is non-commercial desktop distributions such as Debian or Fedora; it could still check for the presence of x264 or FFmpeg (with h264 support) on the system and use it if it's available, and defer the responsibility of licensing to the user or distributor.

Android supports H.264.

I genuinely wonder if it will in the future. Does not the same reasons for pulling H264 from Chrome hold for the Android browser too?

Carriers will put it back.

I'm not sure why Firefox has to support H.264 on all its platforms, but in this case it can, through Flash.

Even if it couldn't, why would it be a bad thing for Firefox to support OS-supplied codecs on OS X and Windows, and a set of built-in codecs, such as WebM, on Linux?

OS codecs are an unquantifiable security risk, since their source code is not available to Mozilla.

Just a theory, but I think before Google's move, hardware decoder would be ubiquitous. Think ION. Think Atom. Think Tegra 2.

H.264 is readily available on Linux.

We had that situation back in the early days of modern mainstream internet. Remember Real Player? WMV embedding? It was not fun.