[SalesForce] Cannot execute batch class from a managed beta

Unfortunately, you have your answer right there, beta packages can't be upgraded.

You will have to uninstall to get to the latest version. SFDC should help you restore your managed package data (in the installed package page) to help you restore your data after the re-install process has completed.

However, if your data structure has changed very much between versions this might not be helpful, and you should review the data you get BEFORE you uninstall.

Indeed an interesting problem, I was not aware Flows deactivation and deletion had this requirement, seems strange. However sure enough it is documented, though the reasoning still seems weak, especially considering, unlike Workflow, there is no scheduled aspect to Flow.

You can’t delete an active flow. Once deactivated, you must wait 12 hours to delete a flow or flow version. This ensures that flows in progress have time to complete. Flows that have never been activated can be deleted immediately.

If I am understanding correctly here, I am assuming you still desire to include it in your package eventually, just not during the Beta package testing phase. During this time you obviously want to be able to develop your Flow, ideally in place where the namespace qualifications are maintained. So you don't have to keep re-editing your file each time you pass it over for testing with your Beta package.

Some thoughts then...

1. Move to Release Package Early. If you are in the part of your development cycle where you are confident about the Custom Objects and global Apex classes in your release. There really is not much to be lost by going to Release package. In this case a lot to be gained, since you can then upgrade your package and thus the flow. This would allow you to put the flow back in your package. It might sound a bit strange, but for the sake of a few minor version increments as you make your final revs to the package ahead of release, moving to Release status during your Beta phase can often help a lot.
2. Multiple DE Test Orgs. You could create a set of DE orgs and cycle them around depending on the age of the Flows you need to delete. Depending on how often your doing releases, maybe 3 or 4 would get your between days. This would allow you to put the Flow back in the package and avoid your editing problem. Downside is it harder to manage with the testers, as they need to know which of your 4 test orgs your using at the time.
3. Designate a DE org with "a" version of your Beta in. Depending on how much the aspects of your package on which your Flow depends apone are changing. You could consider doing your Flow editing in separate org with a fixed version of your Beta in. This is obviously less ideal if things are changing in the package the Flow needs. As I'm not sure of this, thought I'd through this consideration in. In this case the namespaces will not be removed when you save.
4. Eclipse RegEx Find/Replace / Script. If you want to take a bit of sting out of the editing process, it's worth taking a look at the Regular Expression support in Eclipse's Find/Replace dialogue. I've used this effectively in the past for such things, and once you've nailed the RegEx its a few seconds to run it, then copy paste it over to your Beta test package. Even if you get it working partially with a few manual edits it may still save some time.

Thats about it for ideas. Speaking of which I would raise this Flow Dev Life Cycle issue on Ideas, its far from ideal and I am sure it's something that could be addressed easily. Even if for example the platform would say bypass the 12hr wait for Flows that it knows are from a Beta package.

Hope this helps.