What version of LDMS? This sounds like the perfect scenario for Package Bundles in 9.6. You can chain multiple Software Distribution jobs and specify the order in which they run. I use this to deploy VirtualBox, then use a batch file to install the VBox Extensions. It's a great new feature.
I am using LDMS 9.5 SP2, but I remember this option being present in 9.0 SP3 as well:
The Scheduled Tasks created from Distribution packages allow you to define an order of packages (Preliminary, Main, and Final). I use this often when upgrading small programs in our system.
In your case, create two Distribution packages: one for the uninstaller, one for the installer.
Create a scheduled task off of the uninstaller.
In the Properties for that task, look under the option for the Distribution package. You will see a Package order listed near the bottom.
Click on the radio button labelled "Final" and assign your installer Distribution package.
Save the changes and test it out.
Both replies are excellent, thank you.
I tested using the Provisioning template and that worked okay. I have now also looked at the package bundling and the stacking suggested above, which I just never noticed. Guess I should RTFM, huh? Who has the time?
Anyhow, I now have a few ways of accomplishing this task plus some items to add to my toolbelt for the future. Thanks for pointing me in the right direction.