To the original question: I would say "nay". It's the murder of an innocent, pure and simple.
There's nothing to stop the paladin going back in time and giving the innocent a really stern lecture, however.
Now, if there's absolutely no way to stop Mister Villain in the present, and there's going to be absolute destruction of everything, then it's probably reasonable to warn Mister Young Villain that, if he persists on such-and-such a path, you'll beat him to the ground and cut off his thumbs, but that's no different than saying "If you break into the treasury the holy guards will kill you", now, is it?
That's how I'd justify it, at least. Stop the Big Bad. If you have to use force, do so, but by that point, the Little Bad should know that he's going to become a Big Bad if he persists, and that actively seeking evil is probably a big 'HIT ME' sign to paladins.
There, does that solve anything?
ADDENDA: Predestination.
Gods that exist outside conventional time could well give everyone a destiny. The agent of one god might be called upon to stop the agents of another before they become active. In that case, there's no free will involved; the Little Bad will become the Big Bad, and there's nothing you can do about it - except maybe kill him off.
This is a little extreme, though.