> Android is free software in the sense that you can make and distribute modified versions.

I don't think that's enough to make it free software, and "free software in the sense..." is nonsensical. Free software would guarantee the continuance of that freedom. Since that guarantee doesn't exist, Google could place limitations on the Play Store at any time. The fact that they haven't makes the example less clear, but it doesn't make Android free software. Even Google doesn't claim that it is.

Play store isn't part of Android. Even if it was only available to specific phones, that wouldn't make Android unfree.

Play store isn't open source at all.

Amazon was able to take Android and put it on their extremely popular devices with 0 support from Google, no play store. That's what I call freedom

Play store isn't part of AOSP.

> Play store isn't part of Android.

It is extremely well integrated into it, by design.

> Those apps are making a conscious decision to exclude phones/roms not certified by Google. That's their choice.

Isn’t the entire point of Google’s certification process to encourage app vendors to make that choice?

No, only for apps that value certified behavior over accessibility. Typically this is payments (high liability for fraud, higher fraud rates from non-certified users), DRM, and multiplayer gaming (prevent cheating).