Normal soy sauce contains gluten, yes. But you can get "tamari" soy sauce which is pure soy (it's the original, traditional recipe). It's more expensive, but I myself found tamari to not have any ill effects on me, while wheat-based soy sauce sends me to the toilet within 2-5 hours. Small amounts of tamari shouldn't do bad to most people, there are recipes on both Robb Wolf's and Mark Sisson's web sites that use tamari for example.
If you are going out for sushi, simply take with you the tamari sauce bottle and use it. As long as you don't order sushi rolls that contain sauces in them (since they use wheat-based soy sauce as a base), and you mostly go for sashimi, just use your own tamari sauce and you will be fine.
Alternatively, you can go for coconut aminos. It's more expensive than either kinds of soy sauce, but it's a soy-free alternative.