I think I've found a safe place to store stuff early game that doesn't involve joining a faction or killing someone.
The Worker's House at http://www.uesp.net/wiki/Skyrim:Mixwater_Mill isn't occupied and everything in there (nothing very valuable) can be taken without stealing. Most importantly it has 3 chests that have always been empty when I've visited. Location is just off the road between Whiterun and Windhelm. There are no crafting facilities.

I can't verify if the containers respawn or not, but I've been living there scot free for most of my characters. I found the place when I married the mill owner then found out the next house was better for storing stuff.

As far as I know, I haven't lost anything in the containers (not just the chests).

Sounds good. I think I'll try it with my next character.

I guess I don't get why you need a free place. Gold is like water in this game; you can get a house for 5k (Whiterun). So why not just buy the house, and use the storage you never have to worry about?

I guess I don't do the easy moneymaking things much. I had 2 followers devoted to storing gear for me before I could afford the house in Whiterun.

Gold is like water LATER - at first it's a pain. so in the early stages it's mostly it's the annoyance of carrying around all your alchemy and smithing stuff. It's not worth selling back and re-acquiring as the loss in value is too high. In it can affect RP: my current character is so even that there's no way he'd do quests for people unless it involved killing, so he'll never get thane houses. So he needs an easy-to-find storage place, and a home would be better (please give us the -ing CK Bethesda...)

Good to have stop-over storage points. Even if you have a house or three. Thanks! I suspect it will be good for those who have high bounties in holds too. Avoiding unwanted attention? Helpful topic. Thanks for the info!

Fort Greymoor, the chest outside behind the stables has never failed me for a whole 59 levels.
Currently using the chest at the Lunar Forge with a new character, been okay so far but can't offer any garauntees it is 100% safe.

What about LUD's cabin?

I've found that Drelas' Cottage (northwest of Whiterun) has three safe storage containers. The two end tables and the dresser upstairs haven't respawned after 40 game days. The chest at the foot of the bed, however, did respawn, as did the rest of the containers/bags, as well as the crafting items laid out in the open throughout the house. Drelas' Cottage has an alchemy lab and an enchanting table! It is a prime location for anyone who doesn't wish to buy houses in the cities. I'm going to take advantage of it on my next playthrough, for sure.