I've done a lot of work with things like this, hopefully the following will be of some help:
Since you've noted that the computation doesn't have to be performed in real time, this gives you plenty of options. A natural choice, and I see someone has already suggested it, would be a median filter. This usually works pretty well, so long as you choose the window length appropriately. In your example that you showed, it looks like you may need to increase the window size (though it's hard to tell how many samples you have). The main attraction to a median filter is that they will not smear edges, so long as you choose the window size appropriately; most standard smoothing methods will.
If you're over sampled, a legitimate option would be to just reduce your sampling rate and see where that gets you noise wise.
Other smoothing methods exist, but they'll typically smear your edges, and sort of ruin any edge/clock detection you'll want to do. Since you have infinite computation time, median filters are probably your best bet in this realm.
Another option to check out would be a Savizky-Golay filter. This is another data smoothing technique, but it attempts to model the signal using a polynomial. MATLAB has a built-in that works great:
Savitzky-Golay Filtering in MATLAB
I've used this method on varying types of noisy signals, and if you're not constrained to running in real time, you can certainly tweak the parameters and hopefully find a combination that works for you.
Once you've got your data smoothed, a simple threshold would work I imagine. You could statistically set this threshold based on the mean of the smoothed signal (this method assumes that the noise is fairly stationary). Another method would be an edge detection filter, like say the first order derivative of a Gaussian or something. You would convolve this filter with your smoothed signal, and then utilize some peak picking algorithm to get the start/stops of your transitions; this would be a little bit more robust than just utilizing some sort of differentiation filter due to the weights it implicitly applies. You can get the filter in MATLAB by entering: diff(gausswin(sz,alpha)), naturally substituting the parameters for size and alpha that best work for you.
Another option that could forego smoothing with the right implementation is some type of hysteresis thresholding with a "hold" function built into it, given that you have some knowledge or expectation of what the values are when the the pulse isn't present. This would involve having a double threshold, and creating some logic for deciding what values are above and what values are below. The extra bit on top of a traditional hysteresis threshold would be that you'd need to specify some sort of holding mechanism, i.e. a segment is only valid if it breaks the top threshold for X many samples, and it is only invalid if it breaks the lower threshold for Y many samples. This option would probably be the most work, as (from experience, I coded this for my own work fairly recently) it would take you a 100 or so lines of MATLAB code to implement. Setting these thresholds is naturally the challenge here; I've found that a statistical approach is usually robust enough to work.
Last, but certainly not least, you could attempt to do some sort of adaptive filtering if you are able to characterize just the noise component of the signal, and said noise signal is stationary. If you're able to capture just the noise in the signal, through an auxiliary sensor or some clever high pass filtering, you can use the Wiener-Hopf method to clean up the signal. Here's an example:
By statistically characterizing the noise variance (not covariance in this case, since we only have one auxilliary signal) and cross-correlation, we're able to come up with an adaptive weight to remove the noise. For some background theory on this, consult Wiener Filter
Now at the signal is all cleaned up, a simple threshold would get you the edges.
If your noise isn't stationary, you can force it to be stationary in small windows through a process called time segmentation. That's a bit involved though, and hopefully you won't need such a thing.
The MATLAB code that generated that plot is below:
up_s = zeros(1,250)+3;
d_s = zeros(1,500)+3;
u_s = ones(1,500)*10;
s = [up_s,repmat([d_s,u_s],[1,50])];
t = linspace(0,1,numel(s));
% set up the noisy signal
nz = sin(2*pi*500*(t));
snz = s+ nz;
% w = R^-1 r, from wiener-hopf method
% zero mean assumed for covariance and correlation;
% k terms cancel and are excluded
w = inv(nz*nz') * nz*snz';
% apply the weight to the signal
w_sig = snz - w'.*nz;
ax1 = subplot(2,1,1);
ax2 = subplot(2,1,2);
title('Signal Cleaned with Wiener-Hopf Filtering');
Median filtering is great, you just need to select the parameters appropriately for your sample rate. Savitzky-Golay filtering will also get you good results, given that you get the parameters right, which can be challenging. With any smoothing method, you can expect some smearing of the edges, but median filters really minimize this.
If you can characterize just the noise of the signal, you can use an adaptive filter technique like the Wiener-Hopf method; this method assumes that the noise is stationary, so that's something to keep in mind. With this method, you'll get essentially zero smearing of the clocking edges.