How can I repair partition map after attempting to dual boot screwed it up? I tried installing Kali Linux in a separate partition on my MacBook, but after installation was completed, I was unable to boot back into Mac OS (displays a prohibited sign). I think everything went wrong when I let it install GRUB, which may be responsible for the messed up partition map.

I was following this guide http://docs.kali.org/installation/kali-linux-dual-boot-on-mac-hardware, but could not complete the setup of the "Hybrid MBR" because I could not get GDisk, as the MacBook's NIC is not listed in the drivers that came with the distro. Not sure if finishing this step would solve the problem, but at this point I just want to get rid of Kali and get Mac OS back to normal.

As for a reinstallation of the OS from the recovery partition, it doesn't look like this will work, as the Disk Utility is showing all kinds of errors when trying to verify the main volume (see image below). Repair disk doesn't work, by the way. I basically can't reformat anything, all the options are greyed out.

I'm not above wiping the whole drive, but then how will I restore Mac OS? I never had an install disc or anything.

Thanks for any help or ideas!
If your Mac's a Late 2011 or later model you should be able to use Internet Recovery - Apple support page here. You could always install OS X on an external USB/Firewire/Thunderbolt drive which would then give you option of retrieving whatever you need from your internal drive before thoroughly wiping it clean. Personally I like Fedora Linux for this purpose, boot up from USB and go into the Disks utility where you will quickly be able to delete all existing partitions including the hidden EFI section, guaranteeing a clean slate before setting it all up again.

If it's an earlier model then you'll need to find someone with the installer for 10.7/8/9/10 and make a USB installer from it, or find a late retail copy of Snow Leopard (the last copies had 10.6.3 which will start up any Intel Mac before 2011).