Perhaps you are a
Some say I'm impossible / So try me if you dare
A paradox is something that appears impossible.
Some things, before you tackle this beast: / Before me even old men have ceased.
Perhaps a reference to the "grandfather paradox" that apparently forbids time travel? Alternatively, "old" may be "a long time ago" rather than "aged"; some of these paradoxes go back a long long way.
Liars I have found defeated,
A reference to the Epimenides paradox or liar paradox ("this statement is false").
Countless animals I have also cheated.
Not sure what this one is about. Perhaps just the fact that several paradoxes feature animals? (Buridan's ass, Hempel's ravens, the proof that all horses are the same colour, etc.)
Don't point arrows at me, / (You won't get anywhere anyway)
A reference to Zeno's paradox (an arrow shot from A to B has to get half-way from A to B, then half-way from there to B, etc., so how can it ever reach its target? Indeed, before getting half-way from A to B it has to get half-way from A to there, etc., so how can it even get started?)
Don't forget I can be constructive, / As much as I am destructive.
Not sure about this; perhaps the idea is that sometimes a paradox can lead to enlightenment (by forcing you to find a clever way out or -- see e.g. koans in Zen Buddhism -- by bypassing rational thought altogether).
Try as hard as you might, / You won't find the answer to me, / For then I'd surely be no more.
A paradox ceases to be a paradox if a convincing resolution is found.