Anyway. I grew up in PA and spent a few years going to school in Maine so I absolutely understand the "necessity" that comes with an indoor environment and subsequently, a 'dread' mill. But honestly, why would anyone who follows primal, paleo, etc subject themselves to that environment willingly? Agreed. Weak argument dude.
Regardless, from what I do understand a treadmill significantly alters your stride, running form and muscle performance (the difference in propelling yourself against the ground versus having the tread propel you) and would highly suggest not running on it too often.
Finally, trust me when I understand your bias for keys and junk in your pockets when working out. I too hate such things and strive for minimalism as well. I magnet my keys to the wheel well of my car when I go for a jog somewhere backwoods and still haven't truly found out a solution to the headphones/phone thing - but honestly, you probably won't miss the music/podcasts as much as you think.