"Is there a way to output the billing_region & billing_country select fields from Store"
Yes and No.
Yes you can:
{exp:store:checkout disable_form="yes"}
<select name="billing_country">
{billing_country_options}
</select>
{/exp:store:checkout}
Or just the raw values:
{exp:store:cart}
{billing_country} = {billing_country_name}
{/exp:store:cart}
Which can work inside your {exp:user:edit} tags.
But the answer is also No - it will only work when the user has an item in their cart, so if they come back at a later date, or have registered prior to adding products into their cart, the tag pairs will fire the {if no_results} conditional and nothing will get output :(
Other routes - you could use a third_party country/region listing plugin such as Reegion Select by Derek Hogue. But then you may have differences in the references for the countries & regions, which may be important for your payment gateway and syncing with Store on Checkout.
Or I've written a plugin that taps into the Expresso Store classes and outputs the regions or countries independently of the {exp:store:checkout} tags. Although it's still in beta because it doesn't output the JavaScript to update the region select based on the country changing. It'll be on Devot-ee soonish under the name Expresso Store Address.
"the checkbox for setting the shipping info to "Same as Billing Details" is checked and overwrites"
You'll need to force this in your template, something like:
{if "{shipping_country}" != "{billing_country}"}
<input type="checkbox" name="shipping_same_as_billing" value="0" id="deliveryCheckbox">
{if:else}
<input type="checkbox" name="shipping_same_as_billing" value="1" id="deliveryCheckbox" {shipping_same_as_billing_checked} >
{/if}
If you find that the shipping details are still being incorrect displayed in the checkout form data being generated by Store, then you could output the shipping details from the member details instead:
{exp:member:custom_profile_data}{shipping_country}{/exp:member:custom_profile_data}