It's thought that man understood the plan of salvation to some extent, even though Jesus hadn't come yet. It's foreshadowed in the comment to Adam and Eve that Eve's son would crush Satan's head.
Animal sacrifices are recorded as far back as Adam and Eve's children. Through the animal sacrifice system, there was understanding and acceptance that innocent life had to be substituted for forgiveness of sins". And more importantly was the concept that they needed forgiveness and that forgiveness could only be granted by God.
The only way God's plan could be imperfect is if He put the Tree of Knowledge in the garden and didn't know Adam and Eve would eat from it.
I believe that Adam and Eve repented and had Faith in God after the fall. The first killing of animals is God making tunics for Adam and Eve. I think that their Faith was credited to them for righteousness as with the other OT saints.