Você não especificou a arquitetura (amd64 ou ia64 ou qualquer outra?)
Se você estiver usando amd64, lib32gcc1 existe e contém libgcc_s.so.1. Consegui instalá-lo quando tentei.
Se você estiver usando o ia64, você deve usar o ia32-libs-core.
Este link pode informar o pacote necessário para sua arquitetura.
Às vezes, os espelhos do Debian perdem alguns pacotes. Você pode tentar instalar a partir dos principais repositórios dos EUA para ver se é esse o caso.