Without a recovery partition and (for whatever reason) your Internet Recovery just won't work, you are down to about 3 options to get OS X installed:
Option 1: Install (or Recovery) at an Apple Store
If you are close to an Apple Store you can go into one and download the latest OS (if you have a working Mac) or run Internet Recovery using the Apple Network.
Note: Internet Recovery will only install the last version you had, it won't upgrade. For example, if you had Mavericks before and want to go to El Capitan, you will have to recover to Mavericks then download the El Capitan Installer.
Option 2: Download and Make a USB Installer
This involves using another Mac from a friend, family member or acquaintance. You will need an 8GB flash drive. There are many guides on how to create the USB installer so I won't belabor that point here, but the command you will need to execute in Terminal is as follows:
sudo /Applications/Install\ OS\ X\ El\ Capitan.app/Contents/Resources/createinstallmedia --volume /Volumes/<USB Volume> --applicationpath /Applications/Install\ OS\ X\ El\ Capitan.app --nointeraction
<USB Volume> is the name of your USB Flash Drive (don't use spaces - it makes it easier)
After about 10 minutes you will have a USB Flash drive to install OS X on your Mac.
Option 3: Acquire a premade USB Drive
This is not an official recommendation but sometimes when you are in a pinch and Options 1 and 2 are simply not feasible, it's nice to know that there's another option. You can find these on eBay. I have used this option before when I had to restore a Macbook, Internet speed was slightly above dial up and the closest Apple store was in the next State.
Just make sure you you deal with a reputable US based seller with good feedback. If the seller is too new or feedback to low, look elsewhere even if the price is good.