The first questions that comes to mind is: do you use standard PrestaShop check-out or do you have one page checkout module?
From PrestaShop perspective: it chooses default carrier in case it doesn't know what to show, so this is when free shipping comes out in most cases. If you have no free shipping carrier (even if it's disabled), there is no way PrestaShop could choose it. It comes to two possibilities: theme (as you said) or checkout/shipment modules. To understand what is happening, you need developer to investigate it.
So my recommendation (maybe not very helpful) is to hire a freelancer or professional agency, there is no way to solve this issue without looking at the code.