So, I've took all your input and came up for a solution which scales very well. Let's see if anybody can improve it. First again all revised rules with the corrections from your input:
------------
A large group of people (you can assume ~100000) is in the same room, each one sitting on a chair.
No-one knows any other person in the room.
The chairs are not be placed in the room in a specific pattern, they are distributed all over the room.
Suddenly a man enters the room, challenging the people in the room with following task:
"Each one of you has to sit on a different chair than the one you're currently sitting on.
But you aren't allowed to choose the chair you're going to sit on on your own, so let's just say you have to sit on a random different chair.
The probabilites of ending up on each chair haven't to be equally likely, but you may end up on any other chair except the one you're currently sitting on.
You may use supporting tools for that as long you can find them in a normal household or carrying them with you.
You aren't allowed to move any chair. Do that as fast as you can."
------------
0.) While steps 1 to 7 will be processed, the man who entered the room has to determine a random time frame.
You can stop the time it takes for finishing these steps 1 to 7 or shuffle a music library on your PC and take the time of the first song.
1.) Everyone stands up.
2.) Everyone points at his nearest neighbor.
3.) If two people point at each other they found a partner and can sit down.
4.) If anybody pointed at someone who already had found a partner, point at the next nearest neighbor who still stands.
5.) Repeat until no-one or exactly one person remains. If exactly one person remains, this person isn't allowed to take part in steps 6 to 13. For example he can leave the room meanwhile.
6.) One person of each two-person group randomly assigns himself to Group A or Group B. He can flip a coin or guess in which hand his partner has an item.
7.) Everyone from Group A takes of his shoes, stands up, putting one of his shoes on his chair and holding the other one in his hand.
8.) The neutral person switches off the light and everyone from Group A walks around the room. He switches the light on when the time is over. Everyone from Group A has to stop.
9.) Everyone raises one hand.
10.) Everyone points at his nearest neighbor who is in the other group with the other hand.
11.) If two people point at each other they found a partner and can lower their hands.
12.) If anybody pointed at someone who already had found a partner, point at the next nearest neighbor who is in the other group and still has his hand in the air.
13.) Repeat until no-one is left. If in step 5 one person was remaining, repeat until 2 people are left and the remaining person returns to his chair, waiting there standing up.
14.) Everyone from Group A sits on the chair of his partner and gives him his shoe.
15.) Everyone from Group B has to find the chair with the corresponding shoe. His partner can show him the direction to find the chair faster.
16.) If in step 5 one person was remaining, the person from group B who was left over in step 13, has to go to the remaining person and give him his shoe.
17.) He has to find the last chair which is empty.
Some notes:
If two or more people have the exact same shoes, that doesn't matter. In step 15, they sit down if they found the first fitting corresponding shoe.
To be sure, that everyone may end up on any other chair the time frame has to be at least as long as it takes to walk from one end of the room to the other end of the room.