simplest way would be to restore to 1.0.2 software (i'm pretty sure this won't affect your unlocked status, but you will have to re-jailbreak). after doing that, you will have installer. I'd wait for confirmation from first-hand experience before doing that, though.
you also have the option of upgrading to 1.1.1 or 1.1.2, but that is a little more complicated.
Before you go to the hassle of revirginizing and/or restoring, what is the useless crap your talking about? If it is a bunch of programs on the phone that someone installed and you have installer loaded, you should be able to just uninstall the software you no longer wish to use. Unless your having other problems then I would hold off on the other steps until you are sure that is the only way to remove the "useless crap". Please let us know more information about what you need to remove.