How to apply distance-based clustering or dimensionality reduction for too many samples

Maybe you could try Mini-Batch K-Means. I have Matlab code for it:

function [c,counts,idx] = mbkmeans(x,k,c,counts)
    [N,D] = size(x);
    if ~exist('c','var') || isempty(c)
        c = x(1:min([k N]),:) + bsxfun(@times,randn(min([k N]),D)*0.001,std(x));
        if N < k
            c(N+1:k,:) = bsxfun(@plus,mean(x),bsxfun(@times,randn(k-N,D),std(x)));
        end;
    end;
    if ~exist('counts','var') || isempty(counts)
        counts = zeros(k,1);
    end;
    idx = knnsearch(c,x,'k',1);
    add = full(sparse(idx,1,1));
    counts(idx) = counts(idx) + add(idx);
    lr = 1 ./ counts(idx);   
    for i = 1:N
        c(idx(i),:) = (1 - lr(i)) * c(idx(i),:) + lr(i) * x(i,:);
    end;

Usage:

clusters = mbkmeans(yourdata,numberofclusters);

You may feed it your entire dataset at once and you're done. Or you may feed it smaller subsets. In this case, use it like this:

[c1, counts1] = mbkmeans(subset1,numberofclusters);
[c2, counts2] = mbkmeans(subset2,numberofclusters, c1, counts1); %start clustering using previously created clusters
[c3, counts3] = mbkmeans(subset3,numberofclusters, c2, counts2);
...
[cn, countsn, indices] = mbkmeans(subsetn,numberofclusters, c(n-1), counts(n-1));

For R, there is the stream package (explanation here). You may also take a look at this, this and this.