Well, there are some ways to do this.
Widely adopted is using .htaccess, which you said don't wanna use. OK.
You still have some options:
- Using a database table to map everything is one.
- Using a routine to check existing files.
- Using a extended xml sitemap.
- Using a caching system.
Well, everything above can be mixed on your implemetation if you want.
You can find a good article for this on a list apart.
http://www.alistapart.com/articles/succeed/
On this article the solution is a mix:
first check if a file exists (for example "about-us.php");
if yes, include the file contents, else
check db for this request (as a tip, you can have a field named "friendlyURL" on your main content tables).
if exists, extract and display, else
show a 404 page.
as a tip for this one, keeping the SEO feature in mind, I would recommend you to have a sitemap xml. If page is not found, you can check sitemap if is not a broken URL, like:
http://yourdomain.net/shoes/male/bro
you can check if some URL like:
http://yourdomain.net/shoes/male/brown
and suggest it to your customers/visitors. Along with:
http://yourdomain.net/shoes/male/
http://yourdomain.net/shoes/
also a link for your HTML sitemap, and if you have a search feature on your site, also use it, display a link for user go to search page with that query.
http://yourdomain.net/search?q=shoes+male+bro
OR
[input type="text" name="q" value="shoe+male+bro"];
And another extra tech tip: make use of full-text search feature of your db if available.
A interesting reading comes from Rasmus Lerdorf, PHP creator: http://lerdorf.com/lca04.pdf (check page 34, about 404 redirects).