If you have a USB to SATA adapter or drive caddy, you can easily put your new HDD into this, use Disk Utility to partition it with a GUID partition table and format it Mac OS Extended Journaled.
Once that's done, restart your system and hold CMD + R to boot into the Lion recovery mode. From there you can choose to install Lion to your new drive. Once that's done you can migrate from the internal drive so that the new drive is now running Lion and has all of your data.
Now you can safely swap the drives over.
If you have no USB to SATA adapter, or drive caddy, you can create a USB Lion installer with Apple's own Lion Recovery Disk Assistant to install Lion on the new drive, and then restore your data from Time Machine.
You shouldn't need to touch the Leopard DVD this way.