The short answer

You can create a bootx64.efi binary from within the Ubuntu live media with grub-mkimage and write a custom grub.cfg to chainload the loaders you wan't to boot and copy both files to the EFI System Partition (ESP) into the directory \EFI\BOOT\.

If you don't know your way around in the terminal, the script available in the following section of this answer will do this for you. For more details have a look at the Technical details section in The longer answer.

Scripted for your convenience

Regarding this script:

• Be warned that this script installs the grub-efi-amd64 package where it runs and therefore will break legacy MBR installs. Probably only run it from live media if possible.
• Preferably you already know the device name of your ESP.
• You just paste the code below into an open terminal Ctrl+Alt+t and run it Enter.
• You can cancel scripts and programs in terminal with Crtl+c.
• Files on the drive that the live media has been booted from are accessable through /isodevice. GUI: Computer ➜ isodevice in Nautilus/File Manager.

echo -en "\ec"; \
if [ -e "/boot/efi/EFI" ] && [ $(mount | grep -c "/boot/efi type vfat") -gt 0 ]; then \
    esp=$(mount | grep "/boot/efi type vfat" | sed -e 's/ on.*//'); \
    echo "The following device appears to be mounted as an EFI System Partition: $esp"; \
    read -p "Is that correct \"yes\" or \"no\"? Note, that answering \"no\" will unmount $esp! " correctesp; \
    if [ "$correctesp" == "no" ]; then \
        sudo umount "$esp"; \
    elif [ "x$correctesp" != "xyes" ]; then \
        echo "Invalid input, refusing to do anything."; \
    fi; \
fi; \
if ! [ -e "/boot/efi/EFI" ] && ! [ $(mount | grep -c "/boot/efi type vfat") -gt 0 ]; then \
    echo "Possible EFI System Partitions (ESP) found, but none appear to be mounted:"; \
    sudo blkid -t TYPE="vfat"; \
    read -p "Please enter the device name of your ESP (/dev/sd[a-z][1-9]): " esp; \
    sudo mkdir -p "/boot/efi"; \
    if [ "$(echo $esp | cut -c 1-5)" == "/dev/" ]; then \
        sudo mount "$esp" "/boot/efi"; \
    else \
        echo "Invalid input, refusing to do anything."; \
    fi; \
    sudo mkdir -p "/boot/efi/EFI"; \
    correctesp="yes"; \
fi; \
if [ -e "/boot/efi/EFI" ] && [ $(mount | grep -c "/boot/efi type vfat") -gt 0 ] && [ "$correctesp" == "yes" ]; then \
    project="$HOME/uefi-bootfix"; \
    mkdir -p "$project"; \
    echo "--- Begin installing grub-efi-amd64 package (could throw some dpkg errors) ---"; \
    sudo apt-get install -y grub-efi-amd64; \
    echo "--- End of installing grub-efi-amd64 ---"; \
    echo "--- Installing GRUB EFI image and configuration to ESP ---"; \
    grub-mkimage -o "$project/bootx64.efi" -p "/efi/boot" -O x86_64-efi fat iso9660 part_gpt part_msdos normal boot linux configfile loopback chain efifwsetup efi_gop efi_uga ls search search_label search_fs_uuid search_fs_file exfat ext2 ntfs btrfs hfsplus udf; \
    echo -e "set timeout=3\nmenuentry 'Ubuntu' {\n\tchainloader /efi/ubuntu/grubx64.efi\n}\nmenuentry 'Windows' {\n\tchainloader /efi/Microsoft/Boot/bootmgfw.efi\n}\nmenuentry 'Firmware Setup' {\n\tfwsetup\n}\nmenuentry 'ubuntu-14.04.1-desktop-amd64.iso' {\n\tset isofile="/efi/boot/ubuntu-14.04.1-desktop-amd64.iso"\n\tloopback loop $isofile\n\tlinux (loop)/casper/vmlinuz.efi boot=casper iso-scan/filename=$isofile noprompt noeject quiet splash\n\tinitrd (loop)/casper/initrd.lz\n}" > "$project/grub.cfg"; \
    sudo mkdir -p "/boot/efi/EFI/boot"; \
    if [ -e "/boot/efi/EFI/boot/bootx64.efi" ]; then \
        sudo cp -v "/boot/efi/EFI/boot/bootx64.efi" "/boot/efi/EFI/boot/bootx64_uefi-bootfix-backup-$(date +%F_%H-%M-%S).efi"; \
    fi; \
    sudo cp -v "$project/bootx64.efi" "/boot/efi/EFI/boot/bootx64.efi"; \
    sudo cp -v "$project/grub.cfg" "/boot/efi/EFI/boot/grub.cfg"; \
    echo "--- Done. ---"; \
fi

The longer answer

The problem

The UEFI specification recommends firmware implementers to boot via a default bootloader named \EFI\BOOT\BOOT{arch}.EFI for booting from external media, e.g. where relying on NVRAM entries in the platform – the computers' mainboard – to boot a particular operating system is not possible. Currently defined values for arch are x64 for AMD64, ia32 for i386 and ARM orA64 for ARM.

Windows and Fedora install such a bootloader on the ESP, while Ubuntu currently does not. The firmware in some computers – like budget-priced laptops – shows a behaviour where these devices seem to completly ignore correctly registered UEFI bootloaders in the NVRAM bootcatalog and default to booting from \EFI\BOOT\BOOT{arch}.EFI, which will usually result in booting Windows instead of Ubuntu.

Technical details

This configuration currently doesn't support Secure Boot and also hasn't been tested for Apple computers, as I don't own such a machine. (Help is much appreciated.)

If it hasn't been clear until now: This will also allow booting the OS installations on the disk in another UEFI-capable computer, similar to how it has been with legacy MBR.

Generating the bootx64.efi image with GRUB

grub-mkimage -o bootx64.efi -p /efi/boot -O x86_64-efi fat iso9660 part_gpt part_msdos normal boot linux configfile loopback chain efifwsetup efi_gop efi_uga ls search search_label search_fs_uuid search_fs_file exfat ext2 ntfs btrfs hfsplus udf

Creating a corresponding grub.cfg file

This configuration covers the basic cases of booting Ubuntu, booting Windows and launching the firmware setup. The last entry allows for loop mounting and booting an ISO image, which might look odd at first because the ESP usually is only a few hundred megabytes large and can't store such big files, but both files also work on FAT formatted USB drives. A multiboot USB drive with several ISOs is just a few edits away. Also you could easily replace ubuntu with fedora to create another menu entry that boots Fedora or any other Linux distribution, just have a look at the contents of your ESP.

set timeout=3
menuentry 'Ubuntu' {
    chainloader /efi/ubuntu/grubx64.efi
}
menuentry 'Windows' {
    chainloader /efi/Microsoft/Boot/bootmgfw.efi
}
menuentry 'Firmware Setup' {
    fwsetup
}
menuentry 'ubuntu-14.04.1-desktop-amd64.iso' {
    set isofile="/efi/boot/ubuntu-14.04.1-desktop-amd64.iso"
    loopback loop $isofile
    linux (loop)/casper/vmlinuz.efi boot=casper iso-scan/filename=$isofile noprompt noeject quiet splash
    initrd (loop)/casper/initrd.lz
}

Appendix

What about gummiboot and PreLoader?

I have posted something like that in the past and there is nothing wrong with that as far as I can see. It even works with Secure Boot. Good if it worked for you, but the user experience including downloading, creating and extracting several files manually isn't quite optimal and rather difficult for the average user.

Example output

Example output of running the script from live media:

Possible EFI System Partitions (ESP) found, but none appear to be mounted:
/dev/sda1: LABEL="ESP W8" UUID="8AEF-2F66" TYPE="vfat" 
/dev/sdb1: LABEL="ESP HDD" UUID="CBB5-B769" TYPE="vfat" 
/dev/sdc1: LABEL="ESP EVO" UUID="288D-5954" TYPE="vfat" 
/dev/sdd1: LABEL="SANDISK" UUID="B67A-5BFF" TYPE="vfat" 
Please enter the device name of your ESP (/dev/sd[a-z][1-9]): /dev/sdb1
--- Begin installing grub-efi-amd64 package (could throw some dpkg errors) ---
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following extra packages will be installed:
  efibootmgr grub-efi-amd64-bin
The following packages will be REMOVED:
  grub-gfxpayload-lists grub-pc
The following NEW packages will be installed:
  efibootmgr grub-efi-amd64 grub-efi-amd64-bin
0 upgraded, 3 newly installed, 2 to remove and 0 not upgraded.
Need to get 0 B/722 kB of archives.
After this operation, 2,399 kB of additional disk space will be used.
Preconfiguring packages ...
(Reading database ... 169555 files and directories currently installed.)
Removing grub-gfxpayload-lists (0.6) ...
Removing grub-pc (2.02~beta2-9ubuntu1) ...
Processing triggers for man-db (2.6.7.1-1) ...
Selecting previously unselected package efibootmgr.
(Reading database ... 169536 files and directories currently installed.)
Preparing to unpack .../efibootmgr_0.5.4-7ubuntu1_amd64.deb ...
Unpacking efibootmgr (0.5.4-7ubuntu1) ...
Selecting previously unselected package grub-efi-amd64-bin.
Preparing to unpack .../grub-efi-amd64-bin_2.02~beta2-9ubuntu1_amd64.deb ...
Unpacking grub-efi-amd64-bin (2.02~beta2-9ubuntu1) ...
Selecting previously unselected package grub-efi-amd64.
Preparing to unpack .../grub-efi-amd64_2.02~beta2-9ubuntu1_amd64.deb ...
Unpacking grub-efi-amd64 (2.02~beta2-9ubuntu1) ...
Processing triggers for man-db (2.6.7.1-1) ...
Setting up efibootmgr (0.5.4-7ubuntu1) ...
Setting up grub-efi-amd64-bin (2.02~beta2-9ubuntu1) ...
Setting up grub-efi-amd64 (2.02~beta2-9ubuntu1) ...
Installing for x86_64-efi platform.
grub-install: error: failed to get canonical path of `/cow'.
dpkg: error processing package grub-efi-amd64 (--configure):
 subprocess installed post-installation script returned error exit status 1
Errors were encountered while processing:
 grub-efi-amd64
E: Sub-process /usr/bin/dpkg returned an error code (1)
--- End of installing grub-efi-amd64 ---
--- Installing GRUB EFI image and configuration to ESP ---
‘/boot/efi/EFI/boot/bootx64.efi’ -> ‘/boot/efi/EFI/boot/bootx64_uefi-bootfix-backup-2014-11-13_22-39-42.efi’
‘/home/ubuntu/uefi-bootfix/bootx64.efi’ -> ‘/boot/efi/EFI/boot/bootx64.efi’
‘/home/ubuntu/uefi-bootfix/grub.cfg’ -> ‘/boot/efi/EFI/boot/grub.cfg’
--- Done. ---