Hi Jan , et al. sorry to hear about your gun barrel experience, that must of been freaky.
It's hard to really pinpoint or to give an blanket answer like you're all wrong, we're all nice and friendly to don't do it, you'll be shot. All people from all walks of life, social structures, class structures are different... there's a lot of false stereotypes like all NYC folks are nasty, we get the same false impression of Parisians and perhaps all French people in general over here in the US. there's always a few things that you can do to minimize the wackos out there like asking. And when asking, make sure he/she understands that you are a cyclist.. Surely, the bike has an implied meaning of not being a nutcase and probably helps break the ice, so to speak.
Another, is perhaps look up warmshower organizations, like warmshowers.org.
In fact, as a member, I hosted 2 parties of fellow bike tourests in northern NJ who were both on their way to NYC last year. I let them sleep in my living room and take showers, help them with routefinding to NYC and fed them. I think I got more out of it then they did as it is always fun meeting other biketourers.
warmshowers.org is not the only one out there but it goes a bit back and seems to have a good member base.
Hostels are generally fairly inexensive and as you may know, camping at USFS sites are good but they typically exist in national forests and stuff, not everywhere...
If you do stealth camp, I've found that hammocks are usually fast to setup and fairly stealthy and can be pitched in typically more places than tents do and most can be pitched on the ground if you have to. bivy sacks are also small and packable and allow for quick access to it...
Jay