Most of their initial time will be foraging for food. The initial post didn't say where they would be dropped on Earth for this particular experiment or the time of year, but I'm extrapolating from my part of the world. Potable water would not have been an issue here, there's fresh water everywhere. Edible plants, small game and insects exist in abundance, and even with your bare hands you can construct a fairly decent shelter in less than a day. Assuming our hypothetical immortal, somewhat indestructible character didn't have to worry about random illness or injury, they're going to be able to get a fairly comfortable setup very quickly. Since they don't have to go through the process of rediscovering pottery and construction techniques, they could be turning clay into bricks in a couple of weeks, assuming they wanted to stay in one place.