I'm not sure where you got this information. The Android Marketplace arrived with version 1.0 of Android on the T-Mobile G1. Side loading has been available since the very beginning.
What you describe more closely resembles what iPhone did, except that it was never a given that Apple's carrier partners were going to be able to ship their own user facing software on the device.
Operators and OEMs can absolutely customize Android and it was more allowed in the beginning than now. As a way to reduce fragmentation and gain more control over the platform, Google started attaching more and more stipulations to allowing it's suite of software (including Marketplace, now known as Google Play) to be included on handsets.
Was there ever a case of a mobile operator launching their own software store on Android? Certainly OEMs did it, with the Samsung app store being the most prominent. Genuinely curious here, as others do note that (see the Japanese handsets post) OEMs have and even still do a bunch of customization and pre installed apps.