Even after splitting header and footer script, the problem still persist because plugin is called when first wp_enqueue_scripts kicks in, and that’s in the header. So when the plugin or theme calls wp_enqueue_script in the middle of the content (for example, together with the shortcode to make sure script is included only when needed), script will be included in the footer after plugin script as seen on the picture bellow:

Main issue is because we used wp_dequeue_script after said script was added to the plugin so script is practically not enqueued. This will create duplicate code because script will load in the plugin file and from the main source.
Looks like the only solution here is to unset the script url. There are few script registered without url so it shouldn’t brake anything. Good example is jquery. jQuery doesn’t have url in registered scripts instead it’s used to group dependencies jquery-core and jquery-migrate.

This change almost fixed everything but if those scripts were enqueued for the first time in the content, it would still include them after our script.

To fix this completely, we need to split cache_prepare() to css and js counterpart so we can run js part in the wp_footer action.

Edit on April 25: Plugin is finally complete and in working conditions. Here’s the url to the git repository https://github.com/Rustynote/CSS-JS-WordPress-merger.