acid base - Primitive Technology - Production of NaOH

We need to produce NaOH with primitive Technology. This is Part 1 of my Gilligan's Island Challenge series (Part 2). You are stuck on an island with access to a beach, a forest, a river, a lake, and a surface vein of coal.

I realize it can be made from $\ce{NaHCO3 + Ca(OH)2}$, and a person in a primitive technology scenario would be able to make some soda ash, but is there another way? $\ce{NaHCO3}$ might be tough to acquire in substantial quantities without access to a trona mine.

Would adding $\ce{NaCl}$ to a highly basic solution of, say, lime cause $\ce{NaOH}$ to form? If so, could it be extracted? Assume electricity is hard to come by.