Noise reduction from very noisy audio
At the end what has proven to be the best solution was onset detection based on either high frequency or energy content. Before it could work I had to use high-pass filter to cut out first 1 kHz, since it contained too much noise.

Once I had noise-only area I could use its profile to reduce noise from rest of the sample.

One library I found particularly useful was Aubio. It has a good set of examples and provides a lot of algorithms to choose from for onset detection.