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://ift.tt/1C7e4cw, 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!