I could be wrong about this, but...
If you go the Time Machine route, you will restore it back to the exact way it was when you backed it up. So, I don't know how "fresh" you would consider that. Time Machine is more for day to day recovery of deleted files, as well as getting your computer back 100% in an emergency; not so much for selective restoration. But again, I could be wrong about that.
If I were you, I would just back up everything that I needed by simply dragging and dropping it onto the external hard drive. That way, you can reinstall from the Leopard Disc, and have everything "fresh" and squeaky clean, but all of the necessities.
About the installing from CDs thing, I believe if you go from Time Machine the whole installation remains intact, so it should work. But, I don't know how well it would work for larger applications (like ones requiring an installer) with the drag and drop scenario.
Hope this helps.