--Easy on Android

Well Android would definitely work for all 3 of your issues.
1. it's platform is open.
2. Many Android phones are sans keyboard.
3. SDK is free, and it's only $25 to register on their Marketplace.
And as far as time- I'm not a developer, but was able to take sample code from their SDK and get a basic FITALY layout working during my lunch break. - Keyboard layout definitions are just .xml files.

Got it running on my Nexus one now and with some other open source projects I've got predictive text and user dictionaries - next thing I want to get working is integrating the voice recognition APIs into it.

I'm sure a professional developer could get a really polished version running in short order.