Can all waves interfere with each other? What conditions must two waves have such that they interfere? Do they need to have the same frequency or amplitude? Should they pass through a given space at the same time? Should they have the same sources?
 A: 
Can all waves interfere with each other? What conditions must two waves have such that they interfere?

It depends whether one means by waves the solution of sinusoidal equations for energy transfers in a medium, as in water waves, or sound waves, or one means the waves that are solutions to maxwell's equations . 
From your discussion in comments, you are giving the example of light.
All waves that depend for their existence on a medium can interfere  when entering the same space and time coordinates, because energy is a scalar and adds up, and momentum is carried by the medium so the interference can be destructive or constructive. You can observe this in water waves easily.
Light is a different story. Light is not transferred by a medium, as the Michelson Morley experiment showed, and has constant velocity c in vacuum. In addition light is composed by the superposition of an enormous number of photons for that  frequency, of energy = hν,  where h is Planck's constant and ν is the frequency of the light it builds up. So it is a special wave.
Light beams do not interact with each other, i.e. scatter as particles do. Photon-photon scattering is zero to first order and only for very high energy will higher order photon photon scattering have a measurable effect. That is the reason that two light beams can cross without scattering. BUT they can superpose, and their superposition will cause interference patterns if the light beams are coherent, i.e. in phase. It is instructive to see this MIT video on a laser beam split and overlapped, and see the interference of the two beams , and the complicated correlations.
Now in your comment you ask 

What would happen if Red light and Blue light from different sources were to pass through some space at the same time?

There are two problems with this, you have to have spectral blue and red, because observed by our eyes blue and red have many frequencies so there could be no coherence. If a red spectral frequency wave and a blue spectral  frequency wave are in the same (x,y,z,t) nothing will happen because to have a different frequency they are built up by a different source so cannot be coherent, i.e. in phase.
It gets more complicated if one goes to one photon at a time and probability distributions building up the classical electromagnetic wave, but the classical format is fine to explain superposition of light and interference.
A: For two waves to interfere (by which I mean that they produce a stable interference pattern on a screen) they must be coherent i.e., they must maintain a constant phase difference and have same frequency. 
However, the explanation above is naive because the real situation is a bit more complicated due to the fact that no source emits perfectly monochromatic waves. I'll try to give a more detailed answer. 
A: The conditions are as follows:
1) The first condition is obvious, but should be stated for completeness. The waves must overlap in space and time- a wave crossing Pond A  will not interfere with a wave crossing Pond B, nor will a wave on Pond A today interfere with a wave crossing Pond A tomorrow.
2) The waves must not be polarised at right angles to each other. The interference effect occurs in connection with components of displacement in the same direction.
3) Two or more waves will interfere with each other regardless of their respective frequencies and wavelengths- interference simply means that their amplitudes at any point where they overlap is the sum of their individual amplitudes.
4) Random interference of the sort implied by point 3) will produce a random pattern, which is what you observe on the surface of the sea, for example. Random interference in light is not usually noticeable because the effects cancel each other out on average, and happen so quickly (the time is related to the frequencies of the waves involved) and over such tiny areas that your eye has no chance of catching them.
5) If by 'interfere' you meant 'produce a meaningful interference pattern', then there has to be some stable relationship between the frequencies of the waves involved. The frequencies do not need to be exactly the same- indeed the idea of 'beats' in sound arises from waves with slightly different frequencies. However, the simplest case to model is where the waves have the same frequency and a fixed phase relationship.
6) Finally, the waves must be fundamentally capable of interacting with each other. A water wave will not meaningfully interact with a light wave in a manner that would normally be thought of as interference. 
