This is difficult to say without some more info.
I know there are pulsed lasers delivering sub-20fs pulses at around 75 MHz, so 40 MHz should be possible, too. The output power will depend on how you pump them, but 500-1000 mW are realistic. However, for such short pulses, peak powers or the energy per pulse are quantities giving better information. However, I do not know which wavelength you intend to operate at. The above specs are typical for lasers operating around 800 nm. If you want to go to the IR or the blue, yellow or orange spectral regions, things may be more difficult.
Concerning the tuning to the storing ring signal: Typically the central wavelength of the emission is tunable within certain bounds. However, you should consider that even at an optimal time-bandwidth product, a sub-20fs pulse will give you a very broad spectrum. Also for such short pulses one should carefully consider which optics one uses as chromatic dispersion becomes a problem and even a simple element as a beam splitter may spoil your pulse as the bandwidth of the beam splitter might be limited.
You might want to have a look at the web pages of certain laser suppliers which have ultrafast products. I do not want to advertise a special one, so the following are all companies that immediately come to my mind, which might sell laser systems offering the specs you have in mind: Femtolasers, Coherent, Spectra Physics (though I do not know whether they have lasers with <35 fs pulse duration), Toptica Photonics (if you need IR fiber lasers - output power is way lower, though). There might be more, but these come to my mind immediately.