The answer to your question is "no". It's not possible to reword the sentence like you propose without messing up the meaning. You exchanged the object of the sentence.
Ein Mann, den zu beseitigen eine Revolution gelohnt hätte
roughly translates to
A man, whose [possible] extermination would have been worth [starting] a revolution
Ein Mann, den eine Revolution zu beseitigen gelohnt hätte
would translate to somehing like
A man, who would have been worth to exterminate a revolution
(Which obviously doesn't make a lot of sense - It maybe even does in English a bit, but it is hard to translate a messed-up sentence and bring the notion across...)
The infinitive in the relative clause relates directly to the substantive (or article) in the direct neighborhood which is in accusative. Den in the first example, Revolution in the second.
Another difference is, obviously, that "gelohnt" in the first example uses "Revolution" as object of the sentence, while the second example, due to your rewording uses "den" (which is quite a bit uncommon: "lohnen" + acc denotes "worth the [effort|money|pain|...|even "revolution"]", but rather not "the man".)
Your second example works with both word orders (although it changes emphasis in my opinion and the first one would be rather uncommon),
ein Mann, den zu töten ich versucht hatte
ein Mann, den ich zu töten versucht hatte
because the cases are clear ("den" == accusative, "ich" == nominative) and can overrule the word order. The revolution sentence has both substantives in accusative and must rely on the word order. Nothing to do with tenses, though.