Time travel into the future is already theoretically possible. You may not think of it as time travel, but you are still going through a personal slowing in time resulting in your being behind everyone else. Just travel extremely fast- near light speed. Since the theory of relativity states time will have slowed down for you, then when you return everything else will be much older.
So far, no confusing stuff.
As for time travel into the past... that's a bit harder. You'll never exceed light speed, as your combined velocity in 4 dimensions has to equal light speed, which is why it slows in time as you move very fast in space.
Only 'massless' particles can even travel at light speed. Gravity, light, magnetism all move at light speed. In fact, by exploiting their wave/particle duality and phases (crests, troughs), you can even make them move faster than light. Such a case is indistinguishable from moving backwards in time, since any pulse moving faster than light will get to you faster than the original light- so it looks like it comes out before it gets into the phase machine. Though you can't send any information this way; signals always get distorted or erased by this kind of thing.
Others speculate on wormholes to move backwards in time. To bend space into the kind of saddle-shape needed to go backwards, you need a patch of space with negative energy density. It's not certain how we can get that, but certain areas do have it. The spaces between plates for the Casimir effect have negative energy density, since they are less than 'empty' space, which is averagely zero. Particles and anti-particles are another time-traveling possibility, since a positron (anti-electron) is an electron moving backwards in time.
I'll say this about paradoxes: they definitely exist, but many of them aren't very convincing. Many paradoxes rely on you 'not going back now that history is changed'. They fall apart if your future just happen to 'want' to go back and be responsible for the change, even though you can enjoy the benefits in your time. So if you're going to present a paradox, make it one that doesn't depend on human wills.