Is traditional marketing (newspapers, magazines, outdoors, tv, radio..and so on) necessary for a web startup in a tough niche (travel industry)?
When we were a web startup we looked at the mainstream media and traditional marketing channels and pursued the ones where we saw the best return. If we placed an ad in a niche magazine and it created new leads and sustained revenue at a cost that was worth doing then we kept doing it. Just because it isnt' web or email or social it doesn't mean you shouldn't do it. Once you can work out the cost per lead then it doesn't really matter what the channel is; what you know is that for a certain number of $ you can get a certain number of leads/customers/sales.
In a tough niche I guess there can be many factors why it is tough, but one of them is probably going to be competition. If you can find leads/customers/sales through channels that your competitors are not tapping so well I'd focus on those. Jumping into an ad war with competitors is likely to be a money-pit and as a startup, you'll probably not win. If you can, find a nice blue ocean and stay there.