I can't rename the db first and then create the data package, because the source data connection will try to read from the new database name, which of course does not exist on SQL Server (yet).
If you are referring to the Data Deployment Packages, something has to exist before it can pull in data for deployment. If this is not what you mean, then I guess I don't fully understand your problem.
I also can't just rename the database on the SQL Server side and have DDT recreate it, because it complains about the default database filenames already being in use, etc.
This is because when you change the database name, the file group name will remain the same. Change the primary file group data file name so you do not have a conflict of MDF files on your server.
Is there a high-level bullet-point walkthrough of redeploying an existing db onto the same server under a different name? Or is it simply not worth the effort, and I should just deploy to a new server?
Not yet. This is something that will more than likely be added to the framework fairly soon as there are a number of requests of being able to deploy the same structure under different names. We too have this need.