Sorry if this is basic, but others may be having a similar issue, and if this works for you, hopefully they'll be able to follow it as well.
tl;dr: Install from packages built from the driver binary for your distribution.
Choose a distro. I use ElementaryOS which is built around Ubuntu 12.04 LTS. I also installed a 3.11.0 kernel backported from the Saucy repo, so what I recommend will be based on the assumption of running an Ubuntu or Debian based distro. I'm currently using Catalyst 14.3 Beta v1.0 on it with no issues. Update and upgrade your distro, then install the typical build essential packages.
Since Catalyst 13.11, I've only had success installing the drivers from packages built for my distro. Installing directly from the binary almost always breaks everything, the patches don't work, and the packages are simpler to install and remove anyway.
To build the packages, in a terminal, execute the driver binary with the --listpkg option, copy the distro your kernel is based on from the list, then execute it again with --buildpkg=[distro from list]. When it's done, use dpkg -i (or your distro's package installer) on the generated files to install them.
Look for any errors, and download any dependencies. You may have to install the fglrx_* before the fglrx-* packages. After they've all installed properly, execute aticonfig --initial, then reboot.
If it reboots into a black screen, try to ctrl+alt+F1 into a TTY to read through the logs or to uninstall the fglrx* package files, and then delete your /etc/X11/xorg.conf. Reboot. It should load your usual graphical DE. If you're not feeling too defeated, you can try installing some prebuilt packages from your distro's software center.
The last time I let my distro install my graphics drivers was several years ago on Linux Mint through its Driver Manager, which worked well, although the version installed was a little out of date. I imagine most modern repos should have something similar (Additional Drivers? Software Center?) for installing fglrx packages. Try searching for fglrx and installing what you find.
If that works, congratulations, take a break. You can look for more answers later. If it doesn't, at least you tried.