Firstly, you will need an EFI-booted Linux system. If you still have your original install media (CD, DVD, or USB stick), that should usually include an adequate rescue system. It might even have a one-click repair option :).
Alternatively, the Ubuntu community provides an automatic boot-repair image. It claims to support Fedora. If you want to know what it actually does, I suggest you read this third-party explanation in advance.
However, I used a general-purpose rescue system with console tools. As well as supporting EFI boot, I made sure efibootmgr is in the list of packages. It happened to be called GRML and was based on Debian. Here's the information about console tools and grub-efi I discovered while rescuing my Fedora system:
When running a Fedora 18 system booted by EFI, do not run grub2-install. It will claim success, but it breaks the Fedora grub-efi boot system.
The file /boot/EFI/fedora/grub.efi is installed by the grub-efi package. If you do want to reinstall it, use yum reinstall grub-efi. (To do this from a generic rescue system, you can do this after mounting and chrooting into your installed Fedora system). Fedora grub-efi uses the configuration file /boot/EFI/fedora/grub.cfg (presumably generated by grubby). Fedora on EFI won't generate a file at /boot/grub2/grub.cfg. Running grub2-install will replace file grub.efi with an image that tries to read /boot/grub2/grub.cfg, and will therefore fail.
grub2-install installs an EFI boot entry for grub.efi. However, if you have not disabled Secure Boot in your Windows 8-certified firmware, this entry will fail to boot. You need to boot shim.efi instead (ignore shim-fedora.efi; I'm not sure exactly what that is). See below.
You can lose your EFI boot entry for Fedora if your firmware settings are reset. (Manually, or by firmware upgrade, or because firmware is buggy; the latter has been reported in the wild). Here's how to manually create an EFI boot entry for Fedora with Secure Boot:
sudo efibootmgr -c -L Fedora -d /dev/sda -p 100 -l \\EFI\\fedora\\shim.efi
This example uses partition number 100 on the first standard disk recognized by Linux. You should adjust the options -d /dev/sda and -p 100 to identify the filesystem which Fedora mounts at /boot/efi. This is an EFI system partition. The Fedora installer will have created a dedicated ESP for your Fedora install to use, separate from the ESPs used by any other operating system. (This is different from Ubuntu and OpenSUSE).
Note the efibootmgr command requires that you run it from an EFI-booted system.