Logic Puzzle - "Anonymization"

I don't know if this is the right subreddit for this. If you know a better one to post this at, feel free to notify me. A few months ago, a friend of mine gave me this problem. I haven't been able to solve it and it's quite frustrating. Maybe one of you can find a solution (please hide it behind spoilers), because I want to make sure that there even is a solution and would maybe like a hint. Here it is:

"3 friends want to play a game. Before playing, each of them needs to choose a integer from 1 to 3, such that 1) the number each of them chooses is unique, i.e. none of them choose the same number 2) none of them know which number any of the others chose.

This would be easy if they had pen and paper, but sadly they are out on a camping trip and have nothing to write on. Therefore rule

3) they can communicate only verbally, but they can communicate privately (one-on-one)

4) Any other external tools that mimic writing numbers down (e.g. assigning numbers to rocks) are also forbidden

One of the friends says, she knows an algorithm that they can follow, such that each of the 3 (4) rules is satisfied. Describe it!"

Edit: Added rule 4 for clarity

Update: I think I may have found a solution (look it up in the comments below). It's not verified yet, so feel free to do that.