I wrote a small, easy to deploy URL shortener. As it is written in PHP and uses SQLite3 as a data storage then no installation is needed. Just drag and drop the files through FTP to your host, configure the .htaccess file and you are ready to go.
Files are available on github – github.com/robineero/php-url-shortener. There is also database already prepared and SQL script available. Feel free to modify everything according to your needs.