Is it even theoretically possible for a perfect clock to exist? I have heard that even atomic clocks lose a second every billion years or so. That raises the question, is it even theoretically possible for a perfect clock to exist, one that never gains or loses time?
 A: The words "perfect" and "exist" are not compatible. The only way we can imagine perfect things is in our imagination, not in anything that exists. For things that exist, we can ask how close they are to being perfect, but even that question will not have a perfect answer. The best we can do is to estimate how close they are to being perfect. Losing 1 second in a billion years is pretty darn close to being perfect (since it is 1 part in 31,557,600,000,000,000) but it is not perfect and nothing physical can ever be perfect.
A: 
I have heard that even atomic clocks lose a second every billion years or so.

That would be a small misunderstanding on your part. The second now is defined by atomic clocks. So, if all atomic clocks were consistently slow, then that would mean that the definition of a second was wrong... by definition.
That doesn't make sense.
What you read probably said that an atomic clock can not be regulated to better accuracy than plus or minus so-many seconds per billion years. That is to say, if you built an ensemble of atomic clocks, and you let them all run for a billion years without ever correcting them, then you could expect their counts to differ by some small number of seconds at the end of that time.
A: Well, there is no concept of absolute time or a perfect ' tick tock ' in the universe. Phenomena happen at their own rate.
You can't quantify their 'perfection'. You can quantify the errors you made while measuring their physical aspects.
A: Imagine a totally perfect clock. It measures the time in the place where it is situated. Its own proper time. But due to general relativity the speed of time is affected by nearby objects, gravitational fields, spacetime curvature, speed of motion and gravitational waves.
The ideally perfect clock would look not that perfect for anyone who is located in a different place, surrounded by different bodies that curve the spacetime, and moves around at different speeds.
So, even ideally perfect clock would be not that much useful because it would measure its own proper time, in its own reference frame and in its own place relative to other objects, which is surely different than the proper time of any other object.
A: To say that something is perfect, accurate or absolute, is in itself a lie if we consider the realm of our cosmos being governed by the laws of physics - be it classical, modern, or others.
The most convenient way to say is that nothing is absolute in this real world ( ha! I know that the speed of light is constant in vacuum. But, yes, the truthfulness is just unachievable ). Even space and time is not just, because we know the instances where space-time is just not as accurate as it seems to be.
The theories and their related phenomena, of length contraction, time dilation, red/blue shift in macro physical words and gravitational lensing, gravitational waves and much else more in the quantum level, suggests and portrays a world that we live in as something of a ever changing and ever revealing Pandora's box.
A: It seems as though you are asking if a "clock" can exist that isn't impacted by relativity/time dilation.  At the moment, nothing we can observe in the universe is free of time dilation.  We would need to be able to observe or measure a property of the universe or particle that does not suffer any impact of time dilation.
Unfortunately, there are few possible extra-relativistic properties we can even indirectly observe in the universe (quantum entanglement being on the short list).  We would need to have a better understanding and direct measurement capacity of such a property to devise such a "perfect" time dilation free measurement or apparatus.
