I am trying to compare the difference between two means with two pairwise samples. Unfortunately, my data are very far of being normal. What test would you recommend to use in this situation? Should I revert to a nonparametric test?
A paired t-test assumes that the differences are normal: the original values could have any distribution. More precisely, just like with a t-test, the differences don't even have to be normal, just the sampling distribution of the mean. This usually means that with a large enough sample you can use a t-test even without normality because the central limit theorem will kick in.
On the other hand, one can always use a non-parametric test with not too much loss in efficiency.
Your description of your design is not too precise as it allows two interpretations.
First, it is possible that you have a 2 (between) x 2 (within) design (i.e., two groups with two pairwise samples).
Second, it is possible that you have a simple design with one group which was measured two times.
Only in the second case, the answers here apply.
Furthermore, the question if it is really inappropriate to use a t-test for our data is the crucial part of your question. Sometimes this question is difficult in the sense that one may confuse normality of the data with normality of the residuals (crucial in the first interpretations of your design, see here and here) and/or normality of the differences (crucial for the second interpretation, see Aniko's answer).
If the deviation from normality are that serious that you do not want to use a t-test, you should think about using a permutation test instead of the wilcoxon. See the answers to the following two questions for how to make permutations tests using the
coin package for r with dependent samples:
Sounds like a job for the paired Wilcoxon test.
Note that this method compares the medians of the two samples, not their means. In any case, the mean is often not a good estimator when the distributions are not normally distributed, as it is easily biased by extremely low or high values.