If your webhost does not support .htaccess and the web server is Apache...move to a better host.
If your webhost does not support .htaccess and the web server is not Apache, look to see what type of url rewriting it supports. If you still can't...move to a better host.
.htaccess or its equivalent is pretty much an industry standard these days.
Creating tons of index.php files in tons of nested directories, not only introduces a maintenance nightmare, but also introduces a security risk when it comes to fixing bugs they will need to be pushed through any file with duplicated code. This goes back to creating a maintenance nightmare.
As far as i know, some servers trigger .htaccess when you ask them, instead of automatically, you could try asking them, or... move to another host :)
(i'm sorry, were there supposed to be quotation marks there?)
anyway, if all else fails, you could just make 1 page with a big frame, and have all links change the content of the frame and what the user sees on the top remains the same.
Frames are hardly an ideal solution, but the same goes for not having .htaccess support