Android supports multiple non-official stores (read: APK repos). There is no requirement to use the Google Android Market to run Android.

Currently it seems that the Google Market is the largest by a wide margin, but the times they are a-changin'. Amazon is launching a Android specific app store with an interesting sales model. , Samsung, Verizon, etc, etc, also have very small stores. There are also stores unaffiliated with Android or devices like AndAppStore, App Brain, and Appslib.

I make no assertions in regard to said store's quality, but they do exist. Bottom line: Android OS is not irrevocably tied to the Android Market, though it may appear that way based on popular distribution.

The APK container format, Dalvik, and well thought out Android SDK make many apps extremely portable. I expect more stores to pop up with competing propositions, as well as a general quality to improvement given time.