we're limited by the touch screen a lot because there's no physical buttons to feel your way around the virtual keyboard. i used to have a Nokia E63, which had a full keyboard, and i loved it
i would never want an extra attachment to my phone or anything for typing, so the best i've found is Swiftkey. Swype is also good but i've found that i am faster with tapping, as i can use more than one digit
More
(http://i.imgur.com/KVWRcke.png)
there is also Keymonk, which is essentially Swype that you can use with two thumbs. pretty cool and i'm sure you could potentially get great at it, but after a few weeks i was still having some trouble with accuracy. it also hasn't been updated for 4 years..