In short using the VS2005 Setup & Deployment for deploying items to SharePoint is not recommended or not supported.
SharePoint by itself has it well know deployment way called SharePoint Solutions or WSP file. Almost all the items you will want to deployed to SharePoint can be done using WSP(this includes WebPart as well, not only webpart it will allow to add a safe control entry to WebConfig as well). As per your question you are not allowed to use any other tool. To create WSP solution you will not need any extra tool. You can create a WSP file just with notepad (ddf file) & makecab.exe (its avaliable in most of the windows OS).
If you want to make it life simpler try out WSPBuilder and to install the WSP to sharepoint you can use the STSADM command or SharePointInstaller I have been using these tools for past 3 years and they work like charm.
You also have another option of doing it in the Visual Studio just by installing this template VSeWSS version 1.2!