How to boot into internet recovery mode with rEFInd installed

Update - i was able to solve this situation. The simplest solutions evade at times.

In case someone else runs into this, what i did- In the grub menu i was trying to see if i could do something in the command line interface.. Just typed exit & immediately i was popped back onto refind. Immediately booted into OS X & reinstalled refind..

From the results you posted, I can see the GUID for the Recovery partition is wrong. This is partition number 3 in the tables. The correct value in the GPT would be 426F6F74-0000-11AA-AA11-00306543ECAC. The fdisk command also shows the value to be wrong in the MBR table. Here, the correct value should be AB. If you can not boot to your Recovery partition after repairing these tables, then I would assume the contents of the partition is corrupted.

As far as I know, there is no utility in OS X for this type of repair. (Technically, you could use the dd command, but no sane person would attempt using dd to fix this problem.) I would recommend downloading and installing the gdisk command from here. To install, you may have to modify the setting on the "Security & Privacy" pane of the "System Preferences".

To use the gdisk command, you will need to disable System Integrity Protection (SIP). Normally, this can be done while in Recovery mode. Since you can not boot to Recovery mode, you can use a product called "rEFInd". Many Linux users already have this product installed on their Mac computer. If you do not, you can create a USB flash drive version which can be used to disable/enable SIP. The instructions are given here.

Note: Since you have Debian Linux already installed, you may be able to execute gdisk from this operating system. Since I do not have this operating system installed, I am not going to pursue this further. You can obtain more information from this site. Also, gdisk may be available by booting from an external Emergency Disk. If available under Linux or from an Emergency Disk, you will not have to disable SIP.

Once gdisk is installed and SIP is disabled, you will need to make three changes. These changes involve modifying both the GUID Partition Table (GPT) and the Master Boot Record (MBR) partition table. The changes are listed below.

1. Change the type GUID for partition 3 in the GPT from 48465300-0000-11AA-AA11-00306543ECAC to 426F6F74-0000-11AA-AA11-00306543ECAC. Note: gdisk uses a value of AB00 to represent the value 426F6F74-0000-11AA-AA11-00306543ECAC.
2. Make sure the attribute for partition 3 is 0002000000000000. In the example below, I assume the current value for the attribute is 0000000000000000. If not, make the appropriate corrections.
3. Change the id for partition 3 in the MBR table from AF to AB.

In the example below, I create and mounted a sparse image as /dev/disk1. I then used this image as input to the gdisk command. This was done to simulate the conditions on your computer. You will be making changes to your /dev/disk0.

Steelhead:~ davidanderson$ sudo gdisk /dev/disk1
GPT fdisk (gdisk) version 1.0.1

Warning: Devices opened with shared lock will not have their
partition table automatically reloaded!
Partition table scan:
  MBR: hybrid
  BSD: not present
  APM: not present
  GPT: present

Found valid GPT with hybrid MBR; using GPT.

Command (? for help): t
Partition number (1-5): 3
Current type is 'Apple HFS/HFS+'
Hex code or GUID (L to show codes, Enter = AF00): ab00
Changed type of partition to 'Recovery HD'

Command (? for help): x

Expert command (? for help): a
Partition number (1-5): 3
Known attributes are:
0: system partition
1: hide from EFI
2: legacy BIOS bootable
60: read-only
62: hidden
63: do not automount

Attribute value is 0000000000000000. Set fields are:
  No fields set

Toggle which attribute field (0-63, 64 or <Enter> to exit): 49
Have enabled the 'Undefined bit #49' attribute.
Attribute value is 0002000000000000. Set fields are:
49 (Undefined bit #49)

Toggle which attribute field (0-63, 64 or <Enter> to exit): 

Expert command (? for help): r

Recovery/transformation command (? for help): h

WARNING! Hybrid MBRs are flaky and dangerous! If you decide not to use one,
just hit the Enter key at the below prompt and your MBR partition table will
be untouched.

Type from one to three GPT partition numbers, separated by spaces, to be
added to the hybrid MBR, in sequence: 2 3 4
Place EFI GPT (0xEE) partition first in MBR (good for GRUB)? (Y/N): y

Creating entry for GPT partition #2 (MBR partition #2)
Enter an MBR hex code (default AF): af
Set the bootable flag? (Y/N): y

Creating entry for GPT partition #3 (MBR partition #3)
Enter an MBR hex code (default AB): ab
Set the bootable flag? (Y/N): n

Creating entry for GPT partition #4 (MBR partition #4)
Enter an MBR hex code (default 83): 83
Set the bootable flag? (Y/N): n

Recovery/transformation command (? for help): w

Final checks complete. About to write GPT data. THIS WILL OVERWRITE EXISTING
PARTITIONS!!

Do you want to proceed? (Y/N): y
OK; writing new GUID partition table (GPT) to /dev/disk1.
Warning: Devices opened with shared lock will not have their
partition table automatically reloaded!
Warning: The kernel may continue to use old or deleted partitions.
You should reboot or remove the drive.
The operation has completed successfully.
Steelhead:~ davidanderson$ 

At this point, I would restart your Mac.