TLS certificate rollover outside of the web is complex and tangled
On the web, renewing and rolling over TLS certificates is a well understood thing, with best practices that are exemplified by a Let's Encrypt based system. There is a chain of trust starting from the server's certificate and running up to a root certificate that browsers know, and everything except the root certificate is provided to the browser by the web site. Server certificates are rolled over regularly and automatically, and when this happens the website is also provided with the rest of the certificate chain, which it can and should simply serve to browsers. Intermediate certificates roll over periodically, but root certificates almost never do.
However, all of this relies on a crucial property, which is that web server certificates are ephemeral; they're used in the course of a single HTTPS connection and then they're forgotten. This means that clients visiting the website don't have to be updated when the web server certificate chain changes. Only the web server has to change, and the web PKI world has made a collective decision that we can force web servers to change on a regular basis.
(The one thing that requires browsers and other clients to change is changing Certificate Authority root certificates; how slow and hard it is to do that is part of the reason why CA root certificates are extremely long-lived.)
However, you don't always have ephemeral signatures and certificates, at least not naturally. One obvious case is the various forms of code signing, where you will get a signed blob once and then keep it for a long time, periodically re-verifying its signature and chain of trust. As Mozilla has demonstrated, rolling over any of the certificates involved in the signing chain is rather more challenging and being capable of doing it is going to have significant effects on the design of your system.
Very generally, if you want true certificate rollover (where the keys change), you need to have some way of re-signing existing artifacts and then (re-)distributing at least the new signatures and trust chain. If your signatures are detached signatures, stored separately from the blob being signed, you only need to propagate them; if the signatures are part of the blob, you need to re-distribute the whole blob. If you redistribute the whole blob, you need to take care that the only change is to the signature; people will get very unhappy if a new signature and chain causes other changes. You can also contrive more complex schemes where an integrated signature chain can be supplemented by later detached signatures, or signatures in some database maintained by the client program that re-verifies signatures.
(Since what you generally sign is actually a cryptographic hash of the blob, you don't have to keep full copies of every version of everything you've ever signed and still consider valid; it's sufficient to be able to re-sign the hashes. This does prevent you from changing the hash algorithm, though, and you may want to keep copies of the blobs anyway.)
For rolling over intermediate certificates in specific, I think that you only need access to the original end certificate to produce a version re-signed with your new intermediate, and you should be keeping a copy of these certificates anyway. You could then contrive a scheme where if a signature chain fails to verify purely because one of the certificates is out of its validity period, the client attempts to contact your service to get a new version of the end certificate and trust chain (and then saves the result, if it validates). But this scheme still requires the client to contact you periodically to download signature updates that are relevant to it.
In Mozilla's case, they have the advantage that their program is more or less intrinsically used online on the Internet (with small exceptions) and is generally already set to check for updates to various things. Fetching some sort of signature updates for addons would not be a huge change to Firefox's operation in general, although it probably would be a significant change to how addons are verified and perhaps how they're updated.
All of this is an area of TLS certificates and certificate handling that I don't normally think about. Until Mozilla's problem made this quite visible to me, I hadn't even considered how things like code signatures have fundamental operational differences from TLS website certificates.
PS: Short-lived code signing certificates and other non-ephemeral signatures have the obvious and not entirely pleasant side effect that the signed objects only keep working for as long as you maintain your (re-)signing infrastructure. If you decide to stop doing so, existing signed code stops being accepted as soon as its certificates run out. The friendly way to shut down is probably to switch over to extremely long lived certificates before you decommission things.
What usually identifies an intermediate or root TLS certificate
The usual way of describing TLS certificates for things like websites is that they are a chain of trust, where your website's TLS certificate is signed by a Certificate Authority's current intermediate certificate and then that intermediate certificate is signed by the CA's root certificate. For example, you can read about Let's Encrypt's chain of certificates. Some CAs use a chain of multiple intermediate certificates.
(Modern TLS certificates often include a URL to fetch their parent certificate, as covered here.)
But this raises a question, namely how a TLS certificate specifies what its parent certificate is (the certificate that signed it). Until recently, if you had asked me and I had answered off the cuff, I would have guessed that it was based on something like the cryptographic hash of the parent certificate. As it turns out, this is not how it works; instead, as you can find out from actually looking at a certificate, the parent certificate's identity is given by providing its X.509 Subject Name attribute, which identifies both the organization and the intermediate or root certificate's Common Name attribute.
(Okay, there are also Key Identifiers, see here and here. It appears that Key Identifiers are normally exactly that, which is to say that they identify the public key used, not the certificate as such.)
There are some interesting consequences of this that I didn't fully realize or think about before recently. The first is what Let's Encrypt does, which is that it has two versions of its intermediate certificate, one signed by its own root certificate and one signed by IdenTrust. Since they have the same Subject (including Common Name), TLS certificate validation by browsers and other things will accept either. If you inspect the current two Let's Encrypt X3 certificates, you'll find that they also have slightly different key validity periods, presumably because the one signed by the LE root was signed later (about seven months, if we go from the not-before date).
The second is that you can take an existing intermediate certificate and re-issue and re-sign it with new validity dates (and perhaps other modifications to certificate metadata) but the same keypair, the same Subject and Common Name, and so on. This new version of the intermediate certificate can be transparently substituted for the old version because everything that identifies it matches. However, it absolutely must re-use the same public key, because that's the only way to have existing signatures verify correctly.
(This is similar to how in the old days of manual TLS certificate renewal, you could re-use your existing keypair in your new CSR if you wanted to, although it wasn't the recommended practice.)
(See also how TLS certificates specify the hosts they're for which covers server certificates and talks more about X.509 Subject Names.)
PS: Re-signing a certificate this way doesn't require access to its private key, so I believe that if you wanted to, you could re-sign someone else's intermediate certificate with your own CA. I can imagine some potential uses of this under sufficiently weird circumstances, since this would create a setup where with the right certificate chain a single TLS certificate would validate against both a public CA and your internal CA.