Is it possible to create an app store for Android? Is it Legal?

Would it be possible to create an app store for Android that is run completely by a non Google company?<p>Basically, something that gets around piracy and limitations and only sells paid apps. A premium Android App Store if you like.<p>What are the ways in which Google could legally or in other ways try to prevent this?