Actually, it'd be impossible to MQ it for a level 1. The hides for the turn in are nodrop, and the reward is nodrop, and to get to Natimbi requires you be a certain level (like planar gates and such.) Either way, 65 hp on some boots would be sweet.
I took a level 1 to Nedaria's Landing, Abysmal Sea, and Natimbi. No problem at all, just have to be really careful. (And remember that level 1 halfling rogues get hide/sneak)
As soon as he tried to enter Qimini, he was refused. So Natimbi is not level restricted, but deeper zones are.
Thought the hides could be obtained in Natimbi off flesh rippers. Pattern can be purchased. Dont know of any reason it couldnt be done by low level. (if they can survive to loot hides)
Is there a level requirement for Abysmal Sea though, which is where this quest is done at. 1st person, turns in 3 hides, the person getting MQ turns in pattern, then gets boots. Unless there is a level restriction for Abysmal, a level one COULD get this from MQ.
Haven't tried to enter abysmal sea with low level character, but as a druid (55) i can group port into Natimbi. no restriction there on who i can carry in, that i have observed. abysmal, however, needs to use the Maguses. That is level restricted, I believe, tied to your adventurer's stone, but I could be wrong, (and am often). As far as i know the only way to port into abysmal sea is if you are bound there, or by Magus.