Is the idea here that you find a company that agrees to a start date 3-4 months in the future? That seems like a good idea that could work for larger companies. Most startups I've talked to wouldn't go for that.

Yup that's true. Another possibility is taking a bit of a risk and securing the position upon returning. I know a bunch of people who have done that without issue. This might come at the cost of some career advancement, but I'm assuming that's not a top priority for someone asking this question in the first place.