The perchlorates are a problem, but not one that's impossible to deal with. One possible workaround is to have space suits that you never actually bring inside, you just sort of climb in and out through a hatch in the back that docks with the habitat. Similarly with vehicles, they could dock with the habitat so you can get in and out without going outside.
[1] https://images.adsttc.com/media/images/59ce/60f5/b22e/384e/1...
I don't think lava tubes are the only option, though -- they're just probably the best option in terms of most space for the least effort. Mars has a lot of sulfur which can be used to make a kind of sulfur-based concrete that isn't used much on Earth because Portland cement is much more useful and convenient. But let's say you can make building blocks out of sulfur-based concrete or some other native material. (Worst case you make them out of something light and bring them with you from Earth.) You dig a big hole in the dusty soil, then stack blocks igloo-fashion to make a dome in the bottom of the hole. Then you stack some more blocks to make a (relatively) dust-free stairwell, then pile the Martian soid set aside from digging the hole back over the top of everything else. So now you have a strong below-ground compressive structure that you can line with plastic or something and put in an airlock. The weight of the soil above counteracts the air pressure inside.
Ideally most of the habitat-construction work would be done by robots before people get there; that would be some tricky engineering though.