Do stars of a galaxy change their positions relatively to each other? Complete astronomy noob over here who would be happy if he get a simple answer (and who is also aware that this may be not possible)...

I've learned from a tv documentary that the stars at the edge of the galaxy are not traveling more slowely than the ones closer to the center. 

Does this also mean that all stars in a galaxy do not change their positions relatively to each other? 

To put it simply: If I note the relative position of a star compared to our sun, and then do it again 10 (100 / 1000) years later: Are the coordinates of that star identical or will the star be in a different relative position?

I would assume that the star is in a completely different (relative) place given the speed star systems are travelling because the galaxy is rotating AND the "fact" (read: I don't know if this is really a fact) that the solar system is oscillating through the galactic plane.
Stars do in fact move relative to one another within galaxies of all types. The orbital period of stars in a typical spiral galaxy (at around the same distance as the Sun is from the center of the Milky Way) is on the order of hundreds of millions of years. For the Sun it's something like 230 million years (source). A particularly old person (~100 years old), will have been around long enough to see something like one-tenthousandth of 1% of the orbit of stars in this region of the galaxy! Most of these stars simply do not move much relative to us in that amount of time.

The exception to this view of the motions of the stars is the Sagittarius A* (which is not a star at all, but is in fact a supermassive black hole at the center of the Milky Way). The period of stars traveling around it are on the order of 10's of years.



Also, to give you a rough idea of how galaxies look dynamically, here's a link to a particularly nice galaxy simulator implemented in the browser (created by Adrian Price-Whelan).