Normal arrows will work o.k on all golems, you could return to kill golems later when you have more power. Try to have a fairly straight path behind you when you take your first shot then keep walking backwards while shooting. Also running away will cause the opponents to retreat, wait until almost out of sight then repeat.
Managed to kill them after all. I just used a different type of arrows than normal and they went down.
On more thing : who should I ally with in the desert if I want my reputation increased with the rebels? Or they dont have any camps there? I just entered the zone so....
They don't really have any camps there, but the Orcs and Hashishin both follow Beliar and are somewhat closely tied (you'll get into trouble in various Hashishin cities/settlements if the Orcs consider you hostile).
The Nomads are definitely closer to the Rebels than the Hashishin.
Still, the choice is yours, and there's no way to actually ruin your Rebel reputation in the desert.