As far as I know it cannot be done with app.yaml. The reason is, if you took something like what you're describing, eg:
handlers:
- url: /(.*?)/(.*)
script: /\1?id=\2
App Engine would correctly identify that pattern /shoes/red-shoes and route it to /shoes?id=red-shoes. Except it treats /shoes?id=red-shoes as the filename (which obviously doesn't exist) instead of a script + query string.
So, the way to accomplish what you're trying to do would be something like this:
handlers:
- url: /(.*?)/(.*)
script: /mydbhandler.php
The pattern /(.?)/(.) matches patterns like /shoes/red-shoes and sends all such requests to /mydbhandler.php. Inside /mydbhandler.php you should inspect
$_SERVER["REQUEST_URI"]
which will be "/shoes/red-shoes" and handle it from there inside your PHP code.