Why wouldn't Češi nenosí boty doma be accepted as well?
It not sound naturally for me. Better is "Češi nenosí doma boty".
But is that the only permutation of these four words that sounds natural? What are the rules of word order that are in play here?
Here is something: https://en.wikipedia.org/wiki/Czech_word_order#Clitics
Aren't "doma" and "v domě" interchangeable?
Not exactly. At home can be an apartment, a house, a country...
at home = doma
in a house = v domě
Okay, so "v domě" refers to the specific type of building - a house; whereas "doma" is the home as a concept which could include a house. Thanks Tatko.