Najlepiej aby każda część była na osobnej warstwie, tzn. np. jeśli chcesz połączyć tułów psa z głową i ogonem konia, to na innej warstwie musisz mieć tułów, a na innej tą głowę i ogon. Resztę, z tego co opisałeś, robisz prawidłowo. Kolory można zmieniać na wiele sposobów, np. za pomocą Kolory -> Barwienie lub Krzywe lub Balans kolorów. Można również dodać nową, przezroczystą warstwę powyżej warstwy, którą chcesz pokolorować, ustawić jej tryb na kolor i malować po niej wybranymi kolorami tak, jak w tym tutorialu:
http://www.gimpuj.info/index.php/topic,21514.0.html. A tu masz jeszcze tutorial na fotomontaż:
http://www.gimpuj.info/index.php/topic,6186.0.html. Wprawdzie jest on na podmianę twarzy, ale na pewno się przyda.