This is kinda like I was referencing on Twitter, except slightly different.

Tap and hold say 1 and four choices come up for 1, a, b and c within reach of the number 1, a mini-menu of sorts, but it would need to be fast and fluid. Could be displayed the typical N S E W locations, or maybe possibly a semi-circle which appears at the users preference of an angle?

Could have it be an option, so the user could go either old style T9 or with something similar to above.

You could add a quick toggle, on the mini-menu, to make the letters in caps? Maybe even if input is pressed and held the mini-menu doesn't go away, useful if the user is going to be using another letter.

It works in my head.