It is not a matter of whether it is possible or not but whether it is worth doing...
It simply means, every turn, loop through every unit, roll a dice, jackpot you die.
Obviously in big maps, you end up looping through 1000s of units every turn.
Well, realize that its already looping through the same 1000s of units per turn and doing much more complex things with them so I don't think this would be a significant slowdown.
Also, the world-travelling scout can be (partially) rectified by
1: Making some terrains (deserts, ice, tundra, maybe jungles) damage a unit a certain % per turn (you can get the code from C2C or Final Frontier). That way, units in your homeland would be immortal, but if they leave, on long military campaigns or explorations, they will be damaged, or even killed by the hostile terrain.
2: Prevent units from healing outside of your land unless they are on tiles occupied by a "supply train" unit (you can get the code from the Charlemagne mod). This way, 1: you can limit the speed of "Stacks of Doom" since they have to drag slow supply trains or suffer terrain damage (very much a reality of military campaigns) and 2: scouts, spies, explorers and missionaries will be limited in how long they can be abroad.
____________________________
As for your idea to make it so that all units must attack from an adjacent tile, I don't think that is at all realistic.
https://en.wikipedia.org/wiki/Hit-and-run_tactics are a fairly common military doctrine, not to mention guerrilla warfare.
However, as I mentioned above, supply trains would actually do approximately this, significantly slowing down armies. As for how this affects the AI, I'm not sure, but check AI behavior in "Charlemagne", which comes with BTS