Based on my understanding and reading of Wikipedia, phonemes help distinguish one word from another and each phoneme is an "abstraction over of a set (or equivalence class) of speech sounds (phones) that are perceived as equivalent to each other in a given language".
Does it mean that they exist in every language? Or maybe there are languages for which it very hard to define any "fixed" phonemes?
I don't know of any spoken language that can be said not to have phonemes. (Signed languages are a separate, more complicated issue.)
While phonemes are a theoretical abstraction, there are experiments indicating that they're a good abstraction. In particular, the space of possible sounds is continuous in certain ways. And infants younger than five months are pretty much equally good at distinguishing small contrasts anywhere in this continuous space.
After about five months, though, this changes. After that point, infants become much better at distinguishing certain contrasts, and much worse at distinguishing others. And which contrasts are easiest varies by language: French-speaking infants will be better at telling [ta] from [da], while English-speaking infants will be better at telling [ta] from [tʰa].
This is good evidence that we've imposed some sort of mental boundaries on the continuous space of possible sounds, and try to categorize sounds based on those boundaries. Nowadays this is called "categorical perception". And while this can't tell us experimentally exactly how a language's phonemes should be analyzed—it can't give us much insight on the different ways of analyzing the Mandarin vowel system, for example—it indicates that some sort of discrete mental unit exists, and our brains try to transform incoming sounds into those units before analyzing them further.
The status and even definition of "phoneme" is not at all resolved in phonology, so the best answer is "we don't really know". You have mentioned a number of the often-invoked considerations.
The primary question is whether phones exist. A phone is the categorical treatment of speech sound, the reduction of continuous waveforms to a sequence of discrete letters. Most often the letters used to represent sounds are from the IPA, which provides for example vowel letters like <a,æ,ɛ>. There are also micro-adjustment diacritics for "more front", "retracted", "raised" and so on. Unfortunately there are no official acoustic standards for assigning e.g. vowel letters to formants, but there are expert performances like these which tell you what the particular letters are supposed to sound like. Reduction of continuous speech to such letters is the first step in abstracting away from waveforms. The theory is that a phonetic transcription of an utterance is correct iff it satisfies the language-independent "models" of the individual IPA letters (as judged by well-trained experts).
A further abstraction is possible, one which throws away information that derived by applying rules of a particular language. The difference between "top" with [tʰ] and "stop" with [t] is an example: voiceless stops are aspirated in foot-initial position. The phonetic difference can be eliminated from the transcription because it could be supplied by rule (as long as you have a rule that also tells you where the foot begins). There are many reasons why one might want to throw away information, the usual one being "because it is not important". This is similar to telephone filtering, where speech transmitter over phone lines is simplified because we actually can't hear information above 20Khz, and we don't pay any attention to information above 9Khz. The notion of a "phoneme" is based on the idea that some physical differences are "unimportant" in a particular language. Aspiration of consonants in English is thought to be "unimportant" in English, but "important" in Hindi. This is what phonemes are about.
The immediate problem is, how do you define "being important"? This is usually done by reference to "minimal pair", which is two words whose phonetic transcriptions (the phones) are identical except for a single letter, and the two words have different meanings. For example [sɪp, ʃɪp] or [sɪp, zɪp]. It's a bit complicated, because these wors establish that [s] and [z] are different phonemes, also [s] and [ʃ], but we have not yet shown that [s] and [j] or [s] and [t] are different phonemes. Eventually you can establish that all of the English consonants are "phonemes", except [h] and [ŋ], which turn out to be in complementary distribution.
Since "phoneme" is an artifact of a kind of analysis, whether or not all languages have phonemes depends on the analysis that you use. The procedure that I outlined initially treats all phones as being from one phoneme and then distinguishes phoneme α from phoneme β based on the minimal pair test. Therefore, every language has to have at least one phoneme, and you can prove that there are more using the minimal pair test.
I don't think anyone has uncovered a language where there are literally no minimal pairs (for a particular phonological thing), but it's not too hard to find sounds in languages for which there are no strict minimal pairs. An example is [p] versus [b] in Logoori (probably, [p] vs. any segment). The reason is that [p] is a very infrequent sound (it is a modern importation from other languages, so it shows up in words like [epóósta] "post office", which some people pronounce [ebóósta]). There are only about a dozen words with unpredictable [ŋ], and no minimal pairs.
Such cases inspire people to widen the criteria for labeling something as a "phoneme", so an alternative approach is to frame the idea in terms of "phones that are not always the result of applying a rule to something else". In English, aspiration is always the result of applying the rule of aspiration. In this approach, your initial assumption is that everything is a distinct phoneme, but then you discover that α always derives from β by some rule, so α is not really a phoneme, but β is. But every language has to have al least one segment that splits into two, then three... so logically every language must have at least one phoneme.
Incidentally, phonologists generally do not consider the difference between manual languages and spoken languages to be important, so manual languages have phonemes just as spoken languages do. We just use the old terminology that s biased in favor of spoken languages.
