Note: The following answer is in addition to the excellent answer by DVK, on it's own it's insufficient to answer the question
To answer this question we would first have to define what life is. Following the biological descriptive definition of life we get:
Since there is no unequivocal definition of life, the current understanding is descriptive. Life is considered a characteristic of something that exhibits all or most of the following traits:[36][39][40]
- Homeostasis: Regulation of the internal environment to maintain a constant state; for example, electrolyte concentration or sweating to reduce temperature.
- Organization: Being structurally composed of one or more cells — the basic units of life.
- Metabolism: Transformation of energy by converting chemicals and energy into cellular components (anabolism) and decomposing organic matter (catabolism). Living things require energy to maintain internal organization (homeostasis) and to produce the other phenomena associated with life.,[36]
- Growth: Maintenance of a higher rate of anabolism than catabolism. A growing organism increases in size in all of its parts, rather than simply accumulating matter.
- Adaptation: The ability to change over time in response to the environment. This ability is fundamental to the process of evolution and is determined by the organism's heredity, diet, and external factors.
- Response to stimuli: A response can take many forms, from the contraction of a unicellular organism to external chemicals, to complex reactions involving all the senses of multicellular organisms. A response is often expressed by motion; for example, the leaves of a plant turning toward the sun (phototropism), and chemotaxis.
- Reproduction: The ability to produce new individual organisms, either asexually from a single parent organism, or sexually from two parent organisms.[41][42] or "with an error rate below the sustainability threshold."[42]
Source: http://en.wikipedia.org/wiki/Life
So, looking at the above we next can address the actual question. Now we can go the speculative road asking "can be imagine an entirely alien system that fullfills these requirements?" into which category I would categorize all of Hypothetical types of biochemistry (from the currently top voted answer) or we can ask ourselves "which other systems do we know that could potentially fulfill those criteria?". Now, let me present a crazy example: computers. Or rather, a computer connected to a fully automated manufacturing plant, automated mining plant and solar cell plant. Those things could easily fulfill at least 5 out of the 7 criteria and with additional work there is nothing that would stop them from fulfilling the other criteria and thus be considered alive. As the definition is a descriptive definition in certain cases it requires a slightly open interpretation of terms like "cells", "organic" etc., but to prevent it from becoming a cellular definition this seems a reasonable course of interpretation.
In conclusion I do believe it safe to say that life is possible without water.
Now, the actual question is about whether such a system can evolve and then you get in a lot of other murky territory (the likelihood of evolution occurring by chance are... well... let's just say pretty slim) and even disregarding that it's safe to say that such a mechanical system would not evolve by it's own, however it does give a more intuitive argument that life is something far more complex than just "could we get a workable solution when we replace water with methane".