When you stop to think about it, predestination paradoxes don't work if you have sufficient information. If you know your history well enough to know exactly what you did in the "past", you can easily do something different.
You could do a Donnie Darko-style twist, where changing the past is possible but destabilizes things to the point where it must be avoided. You could do a Source Code-style twist, in which time travel doesn't change anything but can create a new timeline alongside the old. But a pure predestination paradox only works in very limited conditions.