Did you try this one (method 2)?
If you don't want to create packages, you can simply run the install script directly, but this is a bit harder in that it won't tell you if any errors occur. However, it usually works, if you make sure to have all the dependencies installed first. It's what I do most of the time to install my drivers, and not counting the times it fails because of missing dependencies, it works for me all the time. You can also use Envy
This is how I do it:
Download the latest 8.3 driver from AMD/ATI's website. Open up a terminal and do the following...
sudo apt-get install build-essential fakeroot dh-make debhelper debconf libstdc++5 dkms ia32-libs
cd /<location of installer>
sudo sh ati-driver-installer-8-3-x86.x86.run
... and let the installer do its thing (just select the automatic installation option). When it finishes, go back to the terminal and type...
sudo aticonfig --initial
sudo aticonfig --overlay-type=Xv
... and reboot.
A few notes on dependencies. Most of the package requirements I gave at the beginning are for package generation so you'll probably won't need them, but it does not hurt to have them in your system. You may also need to install the dependencies specified on ATI's website:
... but they were already installed on my Ubuntu install; make a check with synaptic anyways. ia32-libs is only needed on 64bit systems.