I haven't watched yet the episodes which deal with Sanzo-ikkou's previous lives, so I can't write what happened in details, I can only base on the infos I got.

--> The bishounens in the past

Konzen Douji -->
(Sanzo... he's so pretty**)      

Kenren Taishou -->

Tenpou Gensui -->

Son Goku -->

--> What happened
The story begins with the birth of Seiten Taisen (*yes, Goku*), an heretical-being born from a stone which has absorbed the aura from the Earth and the sky. Beign an heretic, he has golden eyes. The gods of Tenkai, feared by his enormous power, decide to bring him to heaven to keep an eye on him. So they swindl Goku, who doesn't want to come, promising him a lot of food if he would go there. Of course that's not true!*
So Goku is taken in the present of Kanzeon. Now he has the aspect of a child, he wears the golden diadem and heavy chains on his wrists, his feet and his neck. Kanzeon at first doesn't want him here in Tenkai: it's not an orphanage! Suddenly Konzen (Kanzeon's nephew, who is always complaining about how boring life and his paper work are) enters the room. As Goku sees him, he goes near him, taking in hand his long hair. Goku has just said it shines like the sun, when he accidentally tears it! Konzen goes totally mad and yells at Goku calling him "saru", even though Goku is asking "sorry"! Kanzeon grins and accepts to look after Goku there in Tenkai. Of course she won't do it personally, she leaves all to her nephew, ordering him to become Goku's sun. Konzen protests loudly, but he has to accept his aunt's order!

A day doesn't pass without Goku making some disasters. This time he's folded all Konzen's important paper work in paper airplanes! So to avoid Konzen's rage he runs away and hides in a random room. Inside it there's a guy at about his age, called Nataku, who was running away too because he's drawn on the Emeperor's face while he was sleeping. The 2 become immediatly friends, but when Nataku asks Goku his name, he doesn't know what to answer-nobody has still given Goku a name! So the first thing Goku asks Konzen when he comes back to him is to give him a name. Konzen proposes "Saru", but after Goku's insistence he decides "Goku", short and simple to remember!

Incredible but true, Konzen has a friend in Tenkai: Tenpou Gensui, marshal of heaven's western army, who has an office full of books and always in a total mess (when you enter, the book fall on you**). One day, Tenpou goes visit Konzen, and makes immediatly friends with Goku, who calls him Ten-chan. Tenpou has problems with the general of the army, Kenren ("Taishou" is "general"), who has a too carefree and respectless attitude... like his superior Goujun (the dragon king of the western ocean... who in Gensomaden is Hakuryu, yes!) says, if it weren't for Tenpou, Kenren would have been expelled from the army long ago!
Goku makes friends also with Kenren: one day, he was wandering around the Emperor palace, and while running from the guards, he falls in Kenren. Kenren "saves" him from the guards, saying Goku is his "love-child"! They become friends, Goku calls him "Ken-niichan". Kenren is amazed how can Goku go around no problem with those heavy chains (each of them is 20 Kg)!

In Tenkai, the people aren't allowed to kill others. The only one who can is Toushin Nataku Taishi, the god of war. He's sent to the Earth to defeat Gyuumaou. Nataku isn't happy: all the people in Tenkai treat him like a killing puppet. His father Litouten is always saying him: "You are born only to kill. If you die, no-one will care." But Goku says it's not true: he cares about him, because he's a friend of him!
Litouten isn't happy that Goku is a friend of Nataku: his plan is to sit at Emperor's place and Nataku will succede him. And, by the way, it seems Nataku isn't a full kami, but a man-made mix of kami and demon, made by Litouten himself (*sorry, I don't know how.*) Litouten doesn't like Goku at all: the persons chosen as "Toushin Taishi" have a very short life, so when Nataku will die, it's probabily Goku who will take his place... and this will stop all his plans...

The 4 are now friends (*yes, Konzen too, even though he won't never admit it*) and pass their time together, setting fightings at the parties, playing baseball, cleaning Tenpou's office (*desperated enterprise*)... But Kenren is going into serious troubles. Nataku has to go to Earth once again to subdue people who are causing messes. He still feels sick after the battle against Gyuumaou, but the army doesn't seem to care, and wants him to go and fight alone. Kenren doesn't agree with this and protests against the decision. Litouten doesn't loose the occasion and orders that Kenren has to be beaten and imprisoned. Luckily, his commander Goujun frees him, because he agrees too with Kenren's protest, even if he thinks in every case Kenren is a total stupid. Tenpou has the same opinion: it was a mistake making Litouten an enemy, who in fact has ordered Kenren's dismissal as general. Tenpou goes immediatly to Litouten ordering to recall the order, but after Litouten's offensive words, Tenpou punches him saying "excuse me"! But at the end the order is recalled, and now all our heroes have Litouten as enemy (Konzen too, being the next Toushin Taishi's guardian).

One day, Goku overhears Konzen and Tenpou talking about the fact that Litouten wants to kill Goku, he'll probabily order Nataku to do it. Goku runs away (followed by the 2) and arrives in the presence of the Emperor, where also Nataku, Litouten, Kenren and Kanzeon are. Goku asks Nataku if it's true he'll kill him. Litouten doesn't loose time and before Nataku can say something, he orders him to kill Goku. The fight begins: Nataku is going to kill Goku with his sword, but Goku is saved by Kenren. Litouten orders to kill Kenren too. Kenren and Goku go on fighting against Nataku, while Tenpou attacks Litouten. Unfortunately Nataku is really too strong for them and he's almost killing Goku, when Goku finally tell him his name. Heard this, Nataku, instead of stabbing Goku with his sword, stabs his own shoulder. Eveyone is amazed, Nataku faints. Litouten takes him, saying he still can use him as he wants. At this words, Goku goes very mad, and his golden diadem breaks...

Goku, now as Seiten Taisen, has completely lost his mind and attacks everything in front of him. He attacks Litouten, tossing his eye. Kenren and the others don't want this happen, that isn't Goku. But they can't stop him, he's too strong. It's Kanzeon who does it: she punches Goku and makes him faint.

After this, I guess Goku was sent to the prison under the Gogyou mountain. Unfortunately, I don't know this part in details. I've read somewhere that Konzen and the others were all killed by Goku, and that Kanzeon decided to send him under the mountain to avoid him the execution and to keep him safe from Litouten, erasing his memory for not letting him suffer with the remembrances of what he had done.
500 years later, Sanzo finds him and frees him... and the fantastic story of Gensoumaden Saiyuki begins!!

Differences -->
Konzen vs Sanzo --> Both those 2 has a nasty temper, but Sanzo is really more violent and annoyed than Konzen! Konzen is more solemn, more serious... and less proud. He himself said it: "I'm not strong, I haven't a talent for living like Kenren and Tenpou". Also Sanzo is more sad and troubled.
Kenren vs Gojyo --> No differences, I'd say.** Kenren is even more carefree than Gojyo. He seems not going well with Konzen, but not as much as Gojyo with Sanzo.**
Tenpou vs Hakkai --> Tenpou is a chainsmoker!! Then, he's more spontaneous than Hakkai, and more malicious in some way. But they are both very polite, and they like reading... (Tenpou often falls asleep under his books!).
Goku vs Goku --> More childlish, more innocent, more pure and less bratty. He isn't always saying "I'm hungry"!