This is harder than it first appears. Microsoft actually subsidizes vendors for selling machines with Windows installed. So these cheap laptops would actually be a bit more expensive without the Windows installation.
But it could do. I bought a mainstream laptop from a European big-box retailer 17 years ago which came without Windows installed and nothing but a Knoppix CD. It all worked great out of the box. It would work greater still today.
The corporate monopoly in OS software is just as outrageous as the one in browser software. It's time for Brussels to step in.