There are two types of Karmas 'Sakaam Karma' and 'Nishkaam Karma'.
Sakaam Karma is that karma which is done with some desire. Such a karma results in either Paapa or Punya.
Nishkaam Karma is that karma which is performed without any desire.
And the truth is Nishkam Karma is not possible unless you experience Self Realization or JeevanMukti.
Once the state of Super Conciousness is achieved by an individual whatever he does results in Nishkam Karma.
Nishkaam Karma and liberation always co-exist. Unless there is Nishkam Karma there is no liberation and unless there is liberation there is no Nishkaam Karma.
Every one be it a criminal with heinous crimes is also eligible for liberation. So are non vegetarians who kill animals.
The only thing is that the non vegetarians have to wait till they suffer and clean the Paapa or bad deeds they have performed by killing innocent animals
The beauty of God's love for us is that any one even a person with most heinous karma is also eligible for liberation(unless his bad karma is cleaned)
Logic Behind Nishkaam Karma:
We get birth because of our unpaid karma of past lives. The cycle of death and rebirth continues unless there is no karma left in our lets say 'karma account'.
Unless one achieves Self Realization this Karma Account will never close so is the birth and death cycle.
Bhagvad Geeta is thus beautiful and true and practical as it not only tells about liberation but also describes the ways to achieve liberation
Lastly, Geeta or any Vedic Shastras have a deep logic behind the things they say.
It is our inability that we do not understand or do not seek a Guru who will make us understands the logic behind such sayings.