Assumptions: I will be talking about Hermitian (more generally self-adjoint) operators only. This means that I will assume that the operators in question have a set of eigenvectors that span the Hilbert space. As mentioned by tomasz in a comment, this is not exactly necessary, since more general statements can be made, but since we are dealing with basic QM, I figure this simplification is reasonable.
Questions 1 and 2
The statement is that if two operators commute, then there exists a basis for the space that is simultaneously an eigenbasis for both operators. However, if (for instance) one of the operators has two eigenvectors with the same eigenvalue, any linear combination of those two eigenvectors is also an eigenvector of that operator, but that linear combination might not be an eigenvector of the second operator.
Case in point: we consider the states $|l,m\rangle = |1,1\rangle$ and $|l,m\rangle = |1,-1\rangle$. These are both eigenvectors of $\hat{L}^2$ and $\hat{L}_z$. The eigenvalues of $\hat{L}_z$ are $\hbar$ and $-\hbar$, respectively, but the state
$$|1,1\rangle + |1,-1\rangle$$
is clearly not an eigenvector of $\hat{L}_z$, but it is still an eigenvector of $\hat{L}^2$. This is probably why we use the term "mutual" rather than "same". Finally, we form linear combinations of the $|1,m\rangle$ states to get the $l=1$ states that are eigenvectors of, say, $\hat{L}_y$.
As a straight-forward example, consider the following two matrices:
$$L = \left[ {\begin{array}{ccc}
0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1
\end{array}}
\right]$$
and
$$Z = \left[ {\begin{array}{ccc}
0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1
\end{array}}
\right].$$
The vectors $(1,0,0)$, $(0,1,0)$, and $(0,0,1)$ are eigenvectors of both operators. The latter two are eigenvectors of $L$ with the same eigenvalue (namely $1$), but they are eigenvectors of $Z$ with different eigenvalues (namely, $1$ and $-1$). If we instead use the vectors $(0,1,1)$ and $(0,1,-1)$, these are still eigenvectors of $L$ with eigenvalue $1$, but they are no longer eigenvectors of $Z$, as you can verify.
Question 3
As cleverly pointed out by Chris White in a comment, the identity operator commutes with every single other operator, and yet there are operators that don't commute with each other. This is the simplest of counter-examples to your intuition. Commutativity is not a transitive property.
I don't know whether your intuition about the problem was mathematical or physical. If it was physical, then this is something you have to just get used to, because it is part of nature that things work this way. If it is mathematical, then perhaps the counter-example provided above will help.
As a straight-forward example, add to the above matrices the matrix
$$X = \left[ {\begin{array}{ccc}
0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0
\end{array}}
\right]$$
This operator commutes with $L$ but not $Z$.
Question 4
It is certainly okay for two operators that don't commute to share an eigenvector. In fact, $\hat{L}_x$, $\hat{L}_y$, and $\hat{L}_z$ all share an eigenvector: the state $|l,m\rangle = |0, 0\rangle$.
As a more trivial example of operators that share an eigenvector that don't commute, consider the following two:
$$A = \left[ {\begin{array}{ccc}
1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1
\end{array}}
\right]$$
and
$$B = \left[ {\begin{array}{ccc}
1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0
\end{array}}
\right]$$
They clearly share the eigenvector $(1,0,0)$, but the lower blocks of the matrices A and B are respectively the Pauli-$z$ and Pauli-$x$ matrices, which do not commute.
Best Answer
We need what you already proved: the existence of common eigenstates. So, assume that $A$ and $B$ commute, and therefore we can find states $|a,b\rangle$ such that:
$$A|a,b\rangle=a|a,b\rangle, \quad B|a,b\rangle=b|a,b\rangle.$$
The postulates of quantum mechanics state that, if $A$ is an observable, and if the system is in one of the eigenstates of $A$, the measurement of $A$ yields the correspondent eigenvalue (in our notation $a$) with certainty (probability 1). So, in this case, if the system is in the state $|a,b\rangle$ then when we measure $A$ we get $a$ with probability 1, but when we measure $B$ we get $b$ also with probability 1.
Thus, once you prove that $[A,B]=0$ implies the existence of simultaneous eigenstates, then the existence of simultaneous accurate measurement follows from the postulates of quantum mechanics.
For reference about the postulates you can check Shankar's Principles of Quantum mechanics or Sakurai's Modern Quantun Mechanics. The former reference discusses the postulates explicitly in chapter 4, while the latter does not list the postulates but discuss this part about simultaneous measurements in chapter 1 (section 1.4, page 30 in the second edition).