It actually is possible.

Before I continue, these instructions are meant for blank EFI System Partitions (ESP) and will probably overwrite existing files, or not work as expected. At least make backups!

Adding required partitions for different platforms

Platforms: Legacy PC, UEFI-based Windows computer, Apple computer

Add an ESP to an existing installation with MBR

You need to follow these instructions from another installation or live media.

1. Install the grub-efi-amd64-bin package. This will only install the resources needed. It will not switch your existing MBR style installation to UEFI and turn things upside down.

2. Shrink your Ubuntu partition in GParted to make space for an ESP. Recommended sizes for ESPs range from 100 MB to 500 MB, but the files created by following these instructions here will not require more than 2 to 5 megabytes.

   Note: It shouldn't matter where your ESP is located on the disk and shrinking your Ubuntu partition by a few megabytes from the end should be quick and safe. Shrinking at the beginning is not safe. One caveat though, your ESP should be a primary partition and not be part of an extended partition or a logical volume, partition numbers from 1 to 4 are fine, numbers above indicate an extended partition on MBR partition tables.

   Choose FAT32 as filesystem and set the boot flag.

3. Mount the ESP you just created and the root filesystem you shrunk:

   mkdir -p /mnt/esp
   mount $esp_device /mnt/esp
   mkdir -p /mnt/rootfs
   mount $root_device /mnt/rootfs
   

   Note: Replace $esp_device and $root_device with the appropriate devices e.g. /dev/sdb2 and /dev/sdb1. The mountpoints /mnt/esp and /mnt/rootfs are just examples chosen to work with the remaining part of this answer.

   Install GRUB's EFI image and a minimal configuration file with:

   grub-install --efi-directory /mnt/esp --boot-directory /mnt/rootfs/boot --target x86_64-efi --removable $device
   

   Note that $device is the whole device e.g. /dev/sdb, not a partition.

4. That's it, we are already done, but let me try to explain a few things.

   The parameter --target x86_64-efi will ensure that UEFI images and modules will be installed to the given paths. --removable will install the UEFI image to the hardcoded path \EFI\BOOT\BOOT{arch}.EFI for removable media, instead of a distribution specific path. Your grub.cfg in /boot/grub/ should work with both boot methods and a new folder named x86_64-efi should now exist next to i386-pc.

   For completeness, this is the command for non-removable media which writes and relies on NVRAM entries in the platform:

   grub-install --efi-directory /mnt/esp --boot-directory /mnt/rootfs/boot --target x86_64-efi --bootloader-id "Ubuntu" $device
   

   Proper UEFI installations include a line similar to the one below in /etc/fstab, but the setup is functional without and the UEFI image (similar to the MBR bootloader) is usually only written/updated during OS installation.

   UUID=1234-567F /boot/efi vfat defaults 0 1
   

Adding an ESP or GRUB-BBP to an installation with GPT

Adding an ESP to a legacy installation on a GPT partitioned drive is very similar to the above:

1. Install the grub-efi-amd64-bin package.
2. Create a partition with a FAT32 filesystem similar to the instructions above by resizing the root partition and set the boot flag.
3. Mount the partitions and run the grub-install command from above that includes the --removable parameter.

This also works if you just want to boot your exisitng UEFI installation on another computer.

Creating a BIOS Bootable Partition (BBP) for GRUB is a bit different:

1. Install the grub-pc-bin package.

2. Create a partition similar to the instructions above by resizing the root partition and set the bios_grub flag. Choose no filesystem and leave it unformatted.

3. Edit the configuration file /etc/default/grub with administrative rights and add GRUB_DEVICE=/dev/sdb6 to the end. Replace /dev/sdb6 with the actual device name of your BBP. You can use the commandline editor nano to keep thing a simple.

   Install the GRUB MBR image to the BBP with:

   grub-install --boot-directory /mnt/test/boot/ --target i386-pc $device
   

   You might want to remove or comment out the line in /etc/default/grub and add it to the actual installation.

Bonus: Add a partition for Macs on an installation with GPT

I found that the very new Mac (Mac Mini A1347 EMC 2840) I was testing with could boot from a standard FAT32 ESP, even from MBR! Anyways, here we go:

1. Install the grub-efi-amd64-bin, hfsprogs, mactel-boot and mactel-boot-logo (optional) packages. You need to enable the Universe repositories (How do I enable the "Universe" repository from the command line?) and add the current Mactel support PPA (see Mactel Support Community team for more details) to install all of them.

2. Create a partition with an HFS+ filesystem similar to the instructions above by resizing the root partition. This time we need a few megabytes more space, so double the size of the ESP if you had only 5 megabytes or less before. No flag is required.

3. Mount the partitions:

   mkdir -p /mnt/esp-mac
   mount $esp-mac_device /mnt/esp-mac
   mkdir -p /mnt/rootfs
   mount $root_device /mnt/rootfs
   

   Note: I chose $esp-mac_device and /mnt/esp-macto avoid conflicts.

   Run the grub-install command that includes the --removable parameter:

   grub-install --efi-directory /mnt/esp-mac --boot-directory /mnt/rootfs/boot --target x86_64-efi --removable $device
   

   Finally setup up the partition the way a Mac expects it to be:

   sudo hfs-bless /mnt/esp-mac/EFI/BOOT/bootx64.efi
   sudo cp -v /mnt/esp-mac/EFI/BOOT/bootx64.efi /mnt/esp-mac/System/Library/CoreServices/boot.efi
   sudo cp -v /mnt/esp-mac/EFI/BOOT/grub.cfg /mnt/esp-mac/System/Library/CoreServices/grub.cfg
   sudo cp -v /usr/share/mactel-boot/SystemVersion.plist /mnt/esp-mac/System/Library/CoreServices/SystemVersion.plist
   sudo cp -v /usr/share/mactel-boot-logo/ubuntu.icns /mnt/esp-mac/.VolumeIcon.icns
   echo "Dummy kernel for booting" | sudo tee /mnt/esp-mac/mach_kernel
   

   To boot Ubuntu from external media on a Mac you would now just need to press the option key ⌥ or Alt on Windows keyboards and select the right disk.

   

About partition flags, type codes and GUIDs

To be as accurate as possible, the boot flag isn't important to GRUB, by default GRUB searches for UUIDs to find the right filesystem to boot from. Setting the boot flag or the bios_grub flag in GParted usually sets a type (MBR) or GUID (GPT) for the partition.

The benefit of setting the correct type or GUID, besides having a properly working setup, is that these partitions will be hidden in the filemanager. The easiest way to check and change types and GUIDs is via Disks (gnome-disks).

Alternatively you could use parted or gdisk:

• 0xef is the type code for ESP in MBR for use with fdisk
• ef00 is the abbreviated type code for ESP in GPT for use with gdisk
• ef02 is the abbreviated type code for BBP in GPT for use with gdisk

Wikipedia has a big list of GUIDs for GPT.

Commandline equivalents in parted according to the manual are parted $device set partition esp on and parted $device set partition bios_grub on.