What is a minimum sample size for a paired t-test and what is a non-parametric equivalent if data is non-normal? I have 4 sample pairs, let's say (x1, y1),...,(x4, y4). 


*

*What is the minimum sample size for a paired t-test?

*Which assumption should I check for paired t-test? 

*If my data is non-normal, what is an alternative non-parametric test?

 A: With such a small sample size the normality assumption is rather important. You may consider the Wilcoxon signed rank test if you think this assumption is faulty. 
If the population is normally distributed, there is no minimum sample size. If the mean difference is small relative to the population variance, then you will have very little power as well. However, it is possible to get good power even with a very small sample size.  
As an example suppose your pairwise differences were normally distributed with (unknown) variance $\sigma^{2} = 1$. Below are monte carlo estimates (using 10000 sims) of the power for incrementally larger values $0, .5, 1, ..., 5$ of the mean pairwise differences
      Mean Difference  Power
 [1,]             0.0 0.0512
 [2,]             0.5 0.1097
 [3,]             1.0 0.2934
 [4,]             1.5 0.5250
 [5,]             2.0 0.7467
 [6,]             2.5 0.8975
 [7,]             3.0 0.9648
 [8,]             3.5 0.9925
 [9,]             4.0 0.9976
[10,]             4.5 0.9998
[11,]             5.0 0.9999

So we can see that it is possible for the paired $t$-test to still have good power when the mean difference is pretty large in comparison to the variance of the differences (at least 2x as large in this case), even if $n=4$. Please keep in mind that this all goes directly out of the window if the differences are not normally distributed. 
You can look at these powers for other values of the mean difference and variance if you like using the R code below (note: the critical value for the $t$-test when $n=4$ using the usual .05 cutoff is 3.182446. The null value to be tested is assumed to be 0). 
U=seq(0,5,by=.5)
V=U-U
sig=1

for(k in 1:11)
{
   Z=rep(0,10000)
   for(i in 1:10000)
   {
      diffs=rnorm(4,mean=U[k], sd=sig)
      z=(mean(diffs)-0)/(sd(diffs)/sqrt(4))
      Z[i]=z
   }
   V[k] = mean(abs(Z)>3.182446)
}
X=cbind(U,V)
colnames(X)=c("Mean Difference", "Power")
X

A: There is no minimum sample size for a t-test. 
But as @shabbychef noted, you will have very little power.  
A: What is the minimum sample size for a paired t-test?
Generally speaking for the ordinary paired t-test, two pairs is the smallest, yielding 1 d.f. 
Which assumption should I check for paired t-test?
Normally, I'd try to assess all of them, but if you only have 4 pairs, it's just about hopeless to try. You have four pair-differences, from which two d.f. would go to estimating the mean and variance of the differences (the location and scale not mattering for the assumptions), in essence leaving two d.f. to assess changing variance, dependence (in whatever form occur to you to look for, if any) and normality.
If my data is non-normal, what is an alternative non-parametric test?
Paired data: Wilcoxon signed rank test; or sign test; or any number of varieties of permutation test or bootstrap test (depending on how you construct your statistic/what exactly you want to test). All of them still have assumptions, of course.
But the t-test is at least reasonably robust to at least mild non-normality of the differences (and its the differences that are supposed to be normal). If the observations are say, mildly right-skew and not very heavy-tailed, the differences may be indistinguishable from normal even at large sample sizes. That said, there's little reason to avoid the signed rank test if non-normality is the main concern, but with 4 pairs, then you're pretty much stuck with a significance level of 12.5%
