I would have to agree with those who said exile if possible and execution if not. In the scenario you have set up, it does not sound like the remaining members of the society have the wherewithal (time, resources, etc.) to keep this person penned up except possibly through the use of a pit - and who, in that situation, would want to dig such a pit when the time could more profitably be put to finding food or shelter? And then feed him?
As far as the means of execution, plenty have been suggested. Rope, if not currently available, can be made out of many types of vegetation... athough in the circumstances given, I'm not sure I'd worry about breaking his neck quickly for his sake (although I might for the sake of the observers). A large rock thrown from a height onto his head is a little iffy, but if someone has the expertise and willingness to break his neck, that's another possibility. But given the total lack of remorse and intent to repeat the crime, I see no reason for a society with these limitations on its resources to spend those resources on a criminal of this type.
The next question, of course, would be what to do with someone who was less violent, more remorseful, committed a lesser crime, or committed the given crime under duress (or at least claimed to be under duress) or the influence of mind-altering substance (you never know with mushrooms, for example).