From what I’ve read in the dev blogs, it seems they’ve put a LOT of thought into distances that must be traveled for various quests, the amount of time it would take for the player to travel those distances, and what could be included within those distances to make it so the player isn’t just walking through empty fields and forests. I therefore disagree with your statement that the implementation of fast travel would change how the game is meant to be played “by design” - if all the distances are fairly reasonable, then inclusion of fast travel would really be a matter of convenience.
As far as how fast travel could be implemented, M&B: Warband comes to mind. When you start a new game it asks if you want to allow manual saves, or play “Realistic” (i.e. it only allows autosaves, so you can’t reload saves). I think a similar option could be included in CK:D - whenever someone starts a new game they have the option, all on its own, to enable or disable fast travelling.
Regarding not including it altogether, I am of the opinion that it would hurt sales and/or peoples’ opinion of the game. I can see more casual gamers getting frustrated at having to walk back and forth across the map, despite the reasonable distances, and the work that is/will be put into making the world interesting. If it isn’t included, then I can see it becoming one of the first mods for the game that people make.