The phenomenon presented in your question is called "Quantifier Floating".
In English grammar, quantifier floating is the syntactic process by which a subject-related quantifier (all, both, or each) can be separated from the subject and appear in more than one location in a sentence. (directly copied from the link)
This quantifier floating is possible not only with normal verbs, but also with auxiliary verbs.
http://www.aclweb.org/anthology/W13-3730 This page has a few examples of quantifier floating involving auxiliary verbs.
(a) All the boys seemed to be in a good mood when they arrived.
(b) The boys all seemed to be in a good mood when they arrived.
(c) The boys seemed all to be in a good mood when they arrived.
It seems that when the subject is not a personal pronoun, structure "all of..." becomes optional. But when a personal pronoun is the subject, if you want to place "all" before the subject, "all of..." becomes obligatory, as in "all of us".
So why do we do it? I don't know. It's just that there are options from which we can choose, and we just choose one of them.
It seems that "both" and "all" are part of the subject in (1) and (2),
but not in (3). Is this correct?
You are partially correct. It is more complicated than that.
The possible positions if the verb is "be" are shown in (31). We can see that the quantifier "all", which is part of the subject NP "all of my relatives" in (31a), can move to a position after the noun when "of" is deleted, as in (31b), or after the verb, as shown in (31c). It is tantamount to saying that "all" that appears separated from the subject is just a transformed version of "all of", still fully related to subject (but due to lack of my knowledge, I don't know if you can claim that it is a part of the subject or not). In (31d), "all" is part of the NP all of my friends, which is the subject of the complement in square brackets. Notice that here all can move to a position where it splits the nonfinite (infinitive) form of to be, as in (31f), but it cannot move over the infinitive, as shown in (31g).
a. All of my relatives are farmers.
b. My relatives all arefarmers.
c. My relatives are all farmers.
d. I want [all of my friends to be at the airport].
e. I want my friends all to be at the airport.
f. I want my friends to all be at the airport.
g. *I want my friends to be all at the airport.