Apache lets you set a custom script to handle 404 errors. Just get all 404s sent to your perl script. They you can get the requested path from the ENV vars. Unfortunately this will make an entry in your error log every time.
The DirectoryIndex
Set the DirectoryIndex on the root directory to a perl script called thedirectory and set this to execute. The rest of the URL can then be read from the PATH_INFO env var. (I can't think quickly how to make thedirectory have a cgi flag though ...)
ModRewrite
Apache has a module ModRewrite that allows you to rewrite a request on the fly. It's not a relocate that changes the address in the user's browser but an actual server-side rewrite of the path. See http://httpd.apache.org/docs/misc/rewriteguide.html for examples.
Snippets of code should be wrapped in
<code> tags not<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).