This issue happened to me again, but now I know what causes it.
- I was building Emacs from a terminal with gcc 9.3.0 loaded.
- I was launching emacsclient from a terminal with gcc 9.1.0 loaded.
I have libgccjit.so available for both gcc 9.1.0 and 9.3.0. But the version mismatch gave the "gcc not found" error.
Note to self: Ensure that the gcc versions used for building and running emacs are the exact same (incl the minor versions).
On the same note, is it possible for Emacs to give a more informative error that says that libgcc of X.Y.Z version was not found?