There are still some third-class web hosters who do allow the .htaccess files … and turn off the standard module mod_rewrite. But without mod_rewrite, WordPress cannot use pretty permalinks, right? Wrong!
There’s another directive we can use: ErrorDocument.
ErrorDocument 404 /index.php
This will do almost the same as the rewrite rules WordPress offers. It will not work with caching plugins like W3 Total Cache, it will not catch empty searches and other .htaccess tricks you may want to use. So consider this trick as a temporary solution until you have found a real web hoster.