Windows had changed the HD partition map from GUID Partition Table(GPD) to MBR. And made HD a "dynamic disk". This is why Mac Os wasn't able to boot.
So, I've tried 1001 ways to recover. Nothing worked. Interned Recovery gives -2002F error. Macbook pro 2012 can't boot from bootable DVD to use DiskWarrior, Drive Genius or similar. It can't boot from OS X Lion install DVD. I could boot Windows recovery console and tried TestDisk which failed to write something to HFS+. Also tried some Windows third party applications which also failed.
I asked a friend with latest Mavericks(which I had too) to make a Recovery USB using OS X Recovery Disk Assistant v1.0 and make a DMG file from it using Disk Utility and send me over internet. Then I used the TransMac application under Windows and burned DMG on my USB stick. I was able to boot from this USB stick into Recovery Mode and from there I can reinstall Mac Os X Mavericks. Somehow it sees my Ethernet cable and doesn't give error.
Note: that Disk Utility wasn't able to recover partitions. I tried to run DiskWarrior from terminal but it gave me an error. TestDisk didn't run too. I could recover or backup my files using Paragon Rescue Kit for Mac Bootable CD, but there was no need since it's my new macbook and I didn't have much files there. I made a clean installation on a USB stick and run DiskWarrior and Drive Genius, none of them could fix partitions. So I gave up and reformatted HD.
That's probably not the answer on how to fix partitions, but that's how I solved this. If somebody finds a way to fix partitions please post as an answer.