Well, regarding Leifur, you are just as related to him as everyone else of Icelandic ancestry. The fact is that for just about every person alive in Iceland prior to 1350 or so, they are either the ancestors of everyone here, or have no known living descendants at all - and Leifur and his father Eiríkur fall into the second category. There are no (reliable) lines that go back to them, so you are not their descendant. You are related to him, of course, but just like everyone else, it is through his mothers side...she (Þjóðhildur) was the daughter of Jörundur Úlfsson, who had a sister, also named Þjóðhildur, who in turn is one of your ancestors.
You do have some interesting ancestors among the vikings of course (but again, exactly the same set of viking ancestors as everyone else in Iceland)
One of your ancestors was the famous poet and homicidal maniac Egill Skallagrímsson, whose story is told in "Egil's saga". He was the father of Þorgerður, mother of Þorbjörg, mother of Ingveldur, mother of Þorgerður, mother of Yngveldur, mother of Snorri, father of Narfi, father of Snorri, father of Narfi, father of Snorri, father of Ormur, fether of Guttormur, father of Loftur, father of Ólöf, mather of Þorleifur, father of Helga, mother of Kristín, mother of Helga, mother of Marín, mother of Guðrún, mother of Guðrún, mother of Gísli, mother of Gísli, father of Halldór, father of Margrét, mother of Guðrún, mother of Hans Wium, father of Hans Hansson.
Another interesting Ancestor is Jón Arason, the last Catholic bishop of Iceland (who was not allowed to marry, of course, but he had 5 or 6 children with his mistress). One of them was Sigurður, father of Þuríður, mother of Árni, father of Sesselja, mother of Hallgrímur, father of Guðrún, mother of Sigfús, father of Jakob, father of Hans Wium, father of Hans Hansson.
As a side note, here is a chart showing the first few generations of Hans' ancestors, just so that you can see which branches end early: http://farm8.staticflickr.com/7007/6830254225_fa9cc033be_b.j...