I'm not positive, but I think you can add the shipping selection in the shipping form anywhere you want... probably at the end.
Then you would actually update the confirm_cart.php page to add the validation to make sure it is selected before moving onto the payment instead of the confirm.php page where it was before.