Whether a bike has a kickstand is really a personal decision, but what the frame is made of is important. If you're not concerned with scratching the frame, and the frame is reasonable sturdy, then get yourself a kickstand; it'll make the bike more usable, and that's what's important. (I wouldn't attach a kickstand to, say, a carbon frame or a bike with a nice paint job I wanted to keep intact, but most of my bikes have them.)
When your LBS told you that "kickstands don't stay on well", what that means to me is that they're either using bad kickstands, or they don't attach them well. However, there are some bikes that won't fit well with a kickstand (such as many folding bikes and racing bikes). However, a commuter bike that won't take a kickstand isn't nearly as useable as one that will.
I don't have kickstands on my touring bikes, because one is a folding bike and the other is a diamond-frame touring bike. The latter will take a kickstand, but I removed it because a bike with a full touring load won't really stay put with a kickstand. I ended up getting a gadget called a click-stand that's essentially a tentpole with a thing on the end that hooks onto the frame, and also comes with a pair of brake bands (they do just what you'd think). Unfortunately, it takes a minute to deploy and isn't suitable for everyday use, but it perfect for touring.
A bike without a kickstand can be parked by leaning it against a railing, or the end of a bike rack, or even lying it on its side on the ground if you're not locking it up. You can use cable locks combined with a sturdy lock such as a U-lock (or even a bungee cord combined with a lock) to keep the bike steady. My kickstand-less bikes have bungee cords that live on the rear racks for this purpose.
If you want a kickstand, do a little research and order one and attach it. If you're concerned about scratching the paint (you will), you can cut up an old tube and use it to protect the frame. Don't tighten it so much that you crush the frame, but check it every so often and make certain it's reasonably tight.