Back in the pre-iphone dark ages I used to use the fitaly keyboard on my handspring visor. http://www.fitaly.com/fitaly/fitaly.htm

I think ti could still be a good keyboard for phones but they seem to have died off and the layout is patented or something and so there don't seem to be any versions of it for android.