Looking for a Backup/Recreate Solution

Solution 1:

You are about a million miles away from being ready to consider Puppet or Chef.
Worry about your (nonexistent) backups and disaster recovery plan first.

Were I in your shoes (I was 3 years ago), this is what I would do --

Step 0: Get some kind of backup. NOW.
If these machines are really mission critical just plug in a big USB hard drive and grab a tar archive of the whole system (see man tar on your system).
Once you at least have an archive, try to locate the original install media for the system, spin up a virtual machine (use Virtualbox or something similar) and do a clean install of your ancient Linux version.

Now figure out how you would restore to a working state if a meteor should strike and take out your production machines.

STOP
Go no further until you have completed step zero and can restore to a working configuration in the event of a disaster. The Chaos Monkey is watching you.

Step 1: Select, install and configure a backup system.

My recommendation for you would be Bacula. Get it working and get regular backups going.
Perform restore tests to your virtual machine from Step 0 and make sure you can get from a bare clean install back to a working system.

Perform this test frequently from now on. (I do it every 3 months. Seriously.)

Step 2: Get on to a supported release of your operating system.

Take that virtual machine from step zero and test upgrade paths until you find one that works.
Best case? Nice clean easy vendor-supported upgrade.
Worst case? Reinstall and some manual pain and suffering.

While you're doing this you can start looking at tools like Puppet and Chef and thinking about how you want to implement configuration management.

(Don't forget those backups and restore tests once you do the upgrade.

Step 3:* Configuration Management

Now that you have an environment that's not in danger of blowing up you can breathe easy and consider configuration management tools in a calm, planned manner.

You can roll this into step 2 and make it part and parcel of your OS upgrade, or you can stabilize everything manually and then bring in configuration management later -- that's your choice.

When you're ready for this step come back and take a long look through the puppet and chef questions. You may also find interesting information tucked away under configuration-management