Yes. Basically you will want to pass the entire url through a router script using mod_rewrite. The .htaccess file should have something like this:
RewriteEngine On
RewriteBase /
#if it's an existing directory
RewriteCond %{REQUEST_FILENAME} -d [OR]
#...or an existing file
RewriteCond %{REQUEST_FILENAME} -f
#serve it up
RewriteRule ^(.+) - [PT,L]
#else, direct to index.php
RewriteRule ^(.*)$ index.php?url=$1 [QSA,L]
Then, in index.php you can have something like this:
$request = explode('/', $_GET['url']);
Which would have all your clean url segments in the $request array. Once you have those values, you can connect to the database, find what the url represents, and output the page. If it's not found, you can send a 404 header with a "Page not found" message.
header('HTTP/1.0 404 Not Found');
echo '<p>Page not found</p>';
So that's the basic clean url technique. If the url is the earlier, messy one, you would just add some logic to check for that, and redirect to the correct clean url:
if(isset($_GET['cat'])){
//put some logic here
header("Location: http://localhost/".$the_clean_url);
}
This basic technique should solve your problem with some tinkering.