(If you installed from Wubi and need to start recovery mode with nomodeset this could do the trick:
To make ubuntu boot with 'nomodeset' all the time you have to edit a wubi file inside Windows. In Windows open the file 'ubuntuinstallwubildr-disk.cfg' in WordPad
It'll look like this:
loopback loop0 /ubuntu/disks/root.disk
set root=(loop0)
search --set=diskroot -f -n /ubuntu/disks/root.disk
probe --set=diskuuid -u $diskroot
linux /vmlinuz root=UUID=$diskuuid loop=/ubuntu/disks/root.disk preseed/file=/ubuntu/install/preseed.cfg wubi-diskimage ro quiet splash
initrd /initrd.img
boot
On the line that starts with 'linux /vmlinuz root=UUID=$diskuuid....' you have to add nomodeset after 'quiet splash'. Save this file and reboot. )

Boot into Recovery mode, select option 'remount'. Drop into a root shell with network access (the 'netroot' option)

From the command line interface please type the following commands to install the newest amd driver:

login

(Just to make sure you are logged in as user not as root)

sudo apt-get remove --purge xorg-driver-fglrx fglrx*

sudo apt-get remove --purge fglrx*

sudo apt-get install build-essential cdbs fakeroot dh-make debhelper debconf libstdc++6 dkms libqtgui4 wget execstack libelfg0 dh-modaliases

sudo apt-get install --reinstall xserver-xorg-core libgl1-mesa-glx libgl1-mesa-dri

sudo dpkg-reconfigure xserver-xorg

This is just to make sure nothing you did prior to this walkthrough will corrupt the outcome.

cd ~/Downloads

wget --referer=http://support.amd.com radeon-crimson-15.12-15.302-151217a-297685e.zip

unzip radeon-crimson-15.12-15.302-151217a-297685e.zip

cd fglrx-15.302

sudo chmod +x amd-driver-installer-15.302-x86.x86_64.run

sudo sh amd-driver-installer-15.302-x86.x86_64.run

The installer will guide you through the installation, after it's done type:

sudo amdconfig --initial

sudo reboot

Your system should now boot up fine with a graphical interface