Comprei o Swift Key X no Market, estava R$0,18. Eu usei por 30 segundos e não gostei, mas as pessoas que usam falam maravilhas. Tem versão de teste grátis também, caso você seja pão-duro o suficiente para querer economizar 18 centavos.

Ele não é T9, mas você pode habilitar essa opção nele. Ele também faz autocorreção (a la iPhone) e predição de palavras (tenta adivinhar o que você vai escrever antes de você digitar).

Se você for um daqueles paranoicos por privacidade, não compre, porque eles coletam tudo o que você digita, em todos os aplicativos, para poderem melhorar a predição de palavras (é o que eles dizem, pelo menos).

Eu uso o SwiftKey X há alguns meses e gosto bastante.

Putz, o teclado padrão da Samsung faz isso, mas não deve estar disponível para outros aparelhos. Vai ter que fazer isso na força bruta: vai instalando os teclados disponíveis no Market e testando, é o único jeito.