The simple rule is just that pronouns follow different rules from nouns. You can take any noun phrase and apply an 's in order to make it possessive. You can not do the same with a pronoun. Every pronoun has its own possessive form:
I -> my
you -> your
he -> his
she -> her
we -> our
you all (second person plural) -> (someone help me on this one)
they -> their
Note also that they is sometimes used as a singular gender-ambiguous pronoun. In this case it is still converted as the plural to their.
Looking at all three of your examples:
*all of us's friend (a friend of all of us)
Since us is a pronoun (in this case, it's the objective form of we) we need to use a pronoun possessive instead.
all of our friend
Next:
*you and me's picture (a picture of you and me)
Again, we see two pronouns (me is the objective form of I). So the correct form is:
your and my picture
Finally:
*the gift I gave to them's receipt
This one is a little different, since the problem doesn't lie with the usage of pronouns. The object in particular is "the gift", which we referenced directly without the use of the word "it". The problem with this sentence is the existence of the word "gave". Once you add a verb this is no longer a noun phrase, but is now an independent clause. As a clause you must either give it its own sentence, introduce a conjunction, or make it part of a prepositional phrase.
I gave them the gift. Its receipt... (new sentence)
I gave them the gift, and its receipt... (conjunction)
the receipt of the gift I gave to them (prepositional phrase)
Note that in the first two cases we had to introduce the pronoun "it". We could also substitute "it" with the word "the gift" ("the gift's receipt..."). The reason that we had to do this becomes obvious if you consider the rest of the sentence. The receipt is part of a separate clause, so in order to reference something in a previous clause we must either use a pronoun or repeat the object we are bringing back.
On final note, if you wanted the receipt to be part of the predicate then you would follow the same rules:
They lost the gift's receipt. It was the gift I gave to them. (new sentence)
(Someone help me on making this into a conjunctive phrase, please)
They lost the receipt of the gift I gave to them