My understanding is that Time Machine backups are not bootable. Has this changed recently?
[doublepost=1466874399][/doublepost]Your Mac should have shipped with a Restore/Install DVD. Do you still have it? If so, you can boot from it by holding down Command-C. Then use disk utility to format the new drive as Apple Extended Format (Journalled). Then install the OS from the DVD. On reboot, the computer should ask you if you want to transfer data from an older Mac. At that point, connect your Time Machine backup drive and select it. This should copy over all your old files, apps and preferences.
Once you are done, go to the App Store and download and install a fresh copy of El Capitan. This will cause the installer to create a recovery partition. Then run Software Update to update all your software.