A restore from your Time Machine backup will restore everything (OS, apps, user accounts, data). Reinstalling the OS just installs the OS over itself leaving your apps, user accounts and data alone.
As far as Recovery Mode (Command+R) and Internet Recovery (Command+Option+R), I think it was when OS X Lion was released that Apple provided a firmware update to some Mac models. I had a 2010 MBP (came with Snow Leopard installed) that this firmware update applied to and I had the ability to use Internet Recovery (IR). However, it was no good if I never bought OS X Lion from the App Store because I had to enter my AppleID/pswd whenever I used IR to reinstall OS X Lion. As far as the Recovery HD, that is relevant to all models of Macs that meet the OS minimum requirements for OS X beginning with OS X Lion (10.7). Somehow your Recovery HD is missing or corrupt which is why you can't use Recovery Mode. Once you reinstall OS X Mavericks, a Recovery HD will be written again.
I strongly suggest once you get back up and running that you create the USB thumb drive installer after you download OS X Mavericks from the App Store. This way you always have a way to get to the OS X Utilities Menu like the Recovery HD.