Before the fall, Adam and Eve were extremely noble(being almost Angelic they could not die) thus, there was no death and before Adam existed, animals were very noble, just as todays humans are more highly capable of being more noble than animals. In the same way animals before the Fall of Adam, animals were more noble than humans of today in a Certain Sense(One of many examples:Animals do not have human reasoning powers) only. Animals did not die since the environment did not support death, fermentation or decay before the Fall of Adam. For example: even after the Fall of Adam grape juice would not turn to wine because people would live upto 1000 years and there was very very slow decay. But only after the Water Deluge God allowed the reduction of the age limit of man and decay began rapidly. Thus grape juice would decay and turn to wine and for this reason Noah got drunk unknowingly since he did not getting drunk with grape juice before the Deluge.
Before the Fall of Adam, there existed plants and trees which were more nourishing than animal flesh. Hence there was no need for animals to eat other animals since, the then existing highly nourishing plants and trees would supply their needs perfectly. After the Fall of Adam, those highly nourishing plants, began to become extinct, and those animals(For example: t-rex) which relied on them now began to look for alternatives, until the only alternative remaining was the flesh of other animals.
Animals do not sin against the commandments of God because they naturally do not have higher intelligent reasoning capabilities like humans beings have thus they follow instinct. For example: some animals still continue to live unclothed in caves for thousands of years they do not have intelligence to wear suits and build skyscrapers. Thus animals are not "cursed" with suffering. Even humans are not "cursed" or "punished" by God, rather God has withdrawn His Blessings just as a smart father would withdraw a gun from his child if the child uses it to hurt himself or others without stopping or asking for pardon. Adam and Eve abused the gifts, control and freedom and did not even ask for pardon. Thus God withdrew the gifts and powers. Catholic.
The reason why the Infinite God allows animals to suffer the consequences of Original Sin which man caused is because mankind would not tolerate animals easily if they were exempted from suffering the effects of Original Sin. God allowed animals to suffer and die because of Original Sin in order to grant mankind some bare minimum "comfort" in his Journey(unavoidable suffering and death) through this Valley of Tears(life on earth) until he may live worthily to merit Heaven.