A couple of years ago we had a selection of Laptops with no Windows or operating system installed. These were mostly for people who use Linux or other Free/Open Source software. Unfortunately we haven't been able to source Laptops without Windows through the "normal" suppliers for quite a while now.
Today though, things have changed. We still can't get them, but, great news! Zareason has set up a store in New Zealand selling Laptops built from the ground up to run Linux. They are great people and if you're looking for a new laptop you must head on over there to check out their great products.
By the way we aren't related to Zareason at all, except for the fact that we both love open source. So you can take this as an impartial recommendation.