Quase todas as distribuições de segmentação por PC terão uma maneira de instalar o GCC, já que você não pode compilar o kernel do Linux sem ele. Mas nem sempre será instalado por padrão e, mesmo que seja, pode ser removido pelo administrador.
Exemplo: não acho que esteja instalado por padrão no Debian. (Embora o instalador ofereça uma ampla seleção de pacotes a serem instalados, existem muitos conjuntos de pacotes padrão.)
Você certamente não o encontrará instalado (ou possivelmente disponível) em distros Linux incorporadas, já que o GCC é razoavelmente grande, tanto em armazenamento quanto em requisitos de RAM para rodar. Em vez disso, ele é instalado em uma máquina não incorporada e tudo é cross-compilado.