This is somewhat reliant on the industry you are in, and your level of experience. Most professional-level businesses would not object to a 4 week notice period, while if you want to be a waiter or cashier they might just refuse because they "need someone to start right away".
I would humbly suggest that not being willing to wait for a 4-week notice period would generally be a sign this is a poorly run business you don't want to be a part of anyway; but if you are desperate to get a job, you tend to end up being of interest to similarly desperate people. This almost always turns out poorly for everyone involved, so do what you can to not be in such a situation.
I would warn you that demanding an increased notice period because of such high turnover is a warning sign that people hate working there, they don't pay well, etc - or the business could even be going under. But if it's an improvement on being unemployed, then just go in with eyes wide open about the environment. Sometimes you just really need a pay check, and that's OK - do what you have to do to provide for yourself.
Having a 4 week notice period shouldn't prevent you from getting the majority of jobs. For your piece of mind, though, I'd want to look closely at that employment agreement and see just what else they are asking, and what 'penalties' they threaten for not giving appropriate notice. Most employers in the US just say that if you quit with less than the requested notice you will not be re-eligible for rehire at the company, and that's it - but you'll want to read that very closely before you sign.