I think you've identified the root cause here. The single point of failure for the business was it's reliance on a tech giant and it's fickle algorithms. Even if google were perfect that's a precarious position to be in.
Especially for a "brick and mortar business" I can't see why you couldn't try other things - direct marketing, cold calling, events, cards in doctor's offices, whatever else.
Generally, you can, but they are a different beast. You have little way to measure them, they are very time consuming, high risk compared to Ads (because you can't change your cards when you notice a week in that customers don't like some word etc). That's a valid long-term strategy, not something to get you business next week when you're starting.
