Você certamente pode remover o gcc. Em geral, se você encontrar algum pacote que não deseja, basta removê-lo com
sudo aptitude remove packagename
então se o pacote tiver alguma dependência que você quer, apenas responda 'n' quando ele perguntar se deve continuar.
Dito isto, IMHO remover o compilador dá uma falsa sensação de segurança. Se um atacante habilidoso obtiver acesso ao shell, você já perdeu a maior parte da batalha de qualquer maneira. Em segundo lugar, não ter um compilador disponível talvez fizesse sentido quando os servidores estavam rodando em arquiteturas geralmente não disponíveis em PC's, estavam rodando algumas variantes proprietárias do Unix etc. Hoje em dia um PC x86 com Ubuntu não é exatamente difícil ou caro para um invasor pegar suas mãos. por isso, se o compilador não estiver disponível, ele pode simplesmente copiar os binários que quiser.