Kia and bhramarraj, I am uncomfortable with your solution. I think that the random guy would not be able to answer the first question.
So suppose your first person is the Random guy and you ask him "if I were to ask you 'is the second person is the random guy', would you say yes?". Let's break this down into 2 statements:
P - The second person is random
Q - Random guy says P is true
Now the question, as asked to the Random guy, becomes: "is Q true?"
The problem is that the validity of Q cannot be determined a-priori. Not even Random guy himself can know, beforehand, what he would say at any given moment. So there can be no answer to "is Q true?".
I might be wrong, but maybe someone can correct me.