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.