How is a validation set used to tune the hyperparameters in a non-biased way, if the new models depends on the values of these?
This is a standard ML problem: changing hyper-parameters changes the performance of the whole model. Ideally, you'd be cross-validating hyper-parameter choices, not merely comparing on a static validation set. That being said you need to be careful with hyper-parameter optimization because you could overfit these to the peculiarities of your validation set ; cross-validation helps to some extent but really what helps is having a test set that you hardly ever test against. Ideally never before you've chosen your HPs with (cross-) validation. And test-set performance will indicate how much your  HP-optimization procedure was biased.

I'm afraid training from scratch is your only solution. This does not however mean that you have to train until the end and many hyper-parameter optimization techniques out there will help you stop training early enough so you don't waste computational resources on HPs which are not worth it. A good starting point would be this blog post by Criteo's Aloïs Bissuel: Hyper-parameter optimization algorithms: a short review