Ok, so I got a workaround for my problem. I think this will help you as well.
Step 0. Backup everything.
Step 1. Generate a custom modeline using gtf from the command prompt. The syntax is gtf WIDTH HEIGHT REFRESH. Eg. "gtf 1280 720 60". Copy the resulting modeline and add it in the monitor section of your xorg.conf file:
My monitor section:
Make a backup of this xorg.conf file.
# 1280x720 @ 60.00 Hz (GTF) hsync: 44.76 kHz; pclk: 74.48 MHz
ModeLine "1280x720_60.00" 74.5 1280 1336 1
472 1664 720 721 724 746 -hsync +vsync
Option "VendorName" "ATI Proprietary Driver"
Option "ModelName" "Generic Autodetecting Monitor"
Option "DPMS" "true"
Option "PreferredMode" "1280x720"
Step 2. Uninstall fglrx. You do this by executing /usr/share/ati/fglrx-uninstall.sh as superuser (sudo). This step might be unnecessary if you already have fglrx 8.11. You could remove the amdccle database instead. But it seems peope have problem with getting the modeline to actually stick so I suggest a clean reinstall of fglrx.
Step 3. Reinstall fglrx. Please note that I'm using 8.11, for me 8.12 gives me segmentation faults whenever I try to use aticonfig. Make sure you replace the autogenerated xorg.conf with your previous xorg.conf that you backed up in step 1. It must contain the ForceMonitors and modeline entries.
Step 4. Restart X / your computer. It should now have the correct resolution and use the HDMI output even when you TV is turned off during startup.
If you still have problems you could try the following script (I don't need it). In fact, you could try this script before trying anything of the above. If it works, the stuff above should work as well:
Replace the sizeX and sizeY values as appropriate.