É bem simples fazer a compilação cruzada de aplicativos x86 em máquinas AMD64 com gcc. Assegure-se de ter os includes e bibliotecas 32 bits instaladas. Pelo menos, tenha os pacotes ia32-libs (as bibliotecas mínimas) e libc6-dev-i386 (para as inclusões). O gcc estará com suporte a multilib (múltiplas bibliotecas).
apt-get install ia32-libs libc6-dev-i386

A partir daí, basta acrescentar a opção -m32 ao compilador gcc.
gcc -m32 -o hello hello.c

Uma arquitetura em particular (i386, i486, pentium etc.), pode ser especificada com -march.
gcc -m32 -march=i386 -o hello hello.c
Fontes:

Debian AMD64 How-to
Debian AMD64 Faq