I have fireTV 2 since a week and its on-screen keyboard was driving me crazy. 
If you also believe it is the worst keyboard you have ever seen, 
below is my guide how to replace it with a better one.  

It should work without root, as long as you can enable ADB debugging 
and connect to the device using adb. 

*Benefits* New keyboard supports mouse, has qwerty layout and is compatible 
with the web (doesn't force you to go prev/next on the page, so you login 
to your services), will also not get in the way if you are using  external keyboard.


*Before you start*

 - Download LeanKey Keyboard from Google Play. 
 - Install Minimal ADB and fastboot tool from XDA (if you don't have adb already)

*Changing keyboard*

1. Open kindleFire settings, enable ADB debugging and installing apps from unknown sources
2. Note you device IP
4. Copy LeanKey Keyboard apk to your device
3. Install LeanKey Keyboard
4. On your computer, open command line using Minimal ADB and fastboot and enter following commands:

adb connect IP
adb shell
ime enable org.liskovsoft.androidtv.rukeyboard/com.google.leanback.ime.LeanbackImeService
ime set org.liskovsoft.androidtv.rukeyboard/com.google.leanback.ime.LeanbackImeService

Remember to replace IP (marked red) with IP of your device.

That's it. My fireTV is rooted and I did a lot of tweaking in between so please let me 
know if you have any issues following this guide. I believe it should work on unrooted
fireTV (even on stick). 

And if you by a chance know any way to adjust fireTV volume, please let me know. 
That's my next pain point with this device...