Have you considered at trying something like the Swype keyboard? I don't know if it's available for the Fire, but I'm sure there's a tablet version, and it should work on the Nexus 7.

I only have it on my phone (a Galaxy Nexus, coincidentally), but it's really great there. I think it would be very good for a tablet as well.