You can’t rename your new app to the previous name …
But (in theory) you should be able to delete your previous app, wait for Fly’s system to delete any internal references to it (such as from DNS records) and then create a new app called the previous name. I don’t know how long that takes. I would assume there is some kind of housekeeping task, cache purge etc. Since at that point Fly would not know of the previous name. And so as far as it was concerned, it was a new one.