What host doesn't let you run java software? I did a dry run a long time ago with solr and ubuntu under VMware fusion in a half gig VM (or maybe 684 Meg), and it's my impression that solr won't run well in limited memory (sphinx works fine) but it's been a while
You can't run Solr/Lucene properly on Google App Engine(just an example), other software may run better in such circumstances, but its quality is questionable
We used it only for Spanish, it worked well enough (and fast enough). We deployed on bare metal so no hosting provider (appart from the rack space) was in the middle. If you are doing things this "difficult" you'll need at least a VPS of course.
anyway, what if my hosting provider won't let me run Solr or any other java software?