After seeing this discussion here, I think how come Edo-tensei nagato had rinnegan. Nagato's original eyes were normal. He received rinnegan from madara. So his edo tensei form should have had normal eyes not rinnegan, if edo tensei brings the original soul; because his eyes were normal until madara gave him his rinnegan.
I think when a person is brought back by Edo Tensei, that person is revived from the last "checkpoint" of his life, when they were at their strongest. Even if originally Nagato's eyes weren't the Rinnegan, when he died he possessed it, similar to Itachi having a full potential Mangekyo Sharingan, yet he was blinded prior to his death in the last moment of his fight with Sasuke.
Since no other Uchiha was resurrected, nor other Rinnegan user was revived, this could be the only possible conclusion you can deduct from these shinobi (if you don't calculate to be a plot hole), that you're coming back from the time when you had your full strength. For example, look at Madara: he is in his younger ages, not an old grandpa who was shown in the cave with Obito.