Suppose that $A$ and $B$ are matrices that commute. Let $\lambda$ be an eigenvalue for $A$, and let $E_{\lambda}$ be the eigenspace of $A$ corresponding to $\lambda$. Let $\mathbf{v}_1,\ldots,\mathbf{v}_k$ be a basis for $E_{\lambda}$.
I claim that $B$ maps $E_{\lambda}$ to itself; in particular, $B\mathbf{v}_i$ can be expressed as a linear combination of $\mathbf{v}_1,\ldots,\mathbf{v}_k$, for $i=1,\ldots,k$.
To show that $B$ maps $E_{\lambda}$ to itself, it is enough to show that $B\mathbf{v}_i$ lies in $E_{\lambda}$; that is, that if we apply $A$ to $B\mathbf{v}_i$, the result ill be $\lambda(B\mathbf{v}_i)$. This is where the fact that $A$ and $B$ commute comes in. We have:
$$A\Bigl(B\mathbf{v}_i\Bigr) = (AB)\mathbf{v}_i = (BA)\mathbf{v}_i = B\Bigl(A\mathbf{v}_i\Bigr) = B(\lambda\mathbf{v}_i) = \lambda(B\mathbf{v}_i).$$
Therefore, $B\mathbf{v}_i\in E_{\lambda}$, as claimed.
So, now take the basis $\mathbf{v}_1,\ldots,\mathbf{v}_k$, and extend it to a basis for $\mathbf{V}$, $\beta=[\mathbf{v}_1,\ldots,\mathbf{v}_k,\mathbf{v}_{k+1},\ldots,\mathbf{v}_n]$. To find the coordinate matrix of $B$ relative to $\beta$, we compute $B\mathbf{v}_i$ for each $i$, write $B\mathbf{v}_i$ as a linear combination of the vectors in $\beta$, and then place the corresponding coefficients in the $i$th column of the matrix.
When we compute $B\mathbf{v}_1,\ldots,B\mathbf{v}_k$, each of these will lie in $E_{\lambda}$. Therefore, each of these can be expressed as a linear combination of $\mathbf{v}_1,\ldots,\mathbf{v}_k$ (since they form a basis for $E_{\lambda}$. So, to express them as linear combinations of $\beta$, we just add $0$s; we will have:
$$\begin{align*}
B\mathbf{v}_1 &= b_{11}\mathbf{v}_1 + b_{21}\mathbf{v}_2+\cdots+b_{k1}\mathbf{v}_k + 0\mathbf{v}_{k+1}+\cdots + 0\mathbf{v}_n\\
B\mathbf{v}_2 &= b_{12}\mathbf{v}_1 + b_{22}\mathbf{v}_2 + \cdots +b_{k2}\mathbf{v}_k + 0\mathbf{v}_{k+1}+\cdots + 0\mathbf{v}_n\\
&\vdots\\
B\mathbf{v}_k &= b_{1k}\mathbf{v}_1 + b_{2k}\mathbf{v}_2 + \cdots + b_{kk}\mathbf{v}_k + 0\mathbf{v}_{k+1}+\cdots + 0\mathbf{v}_n
\end{align*}$$
where $b_{ij}$ are some scalars (some possibly equal to $0$). So the matrix of $B$ relative to $\beta$ would start off something like:
$$\left(\begin{array}{ccccccc}
b_{11} & b_{12} & \cdots & b_{1k} & * & \cdots & *\\
b_{21} & b_{22} & \cdots & b_{2k} & * & \cdots & *\\
\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots\\
b_{k1} & b_{k2} & \cdots & b_{kk} & * & \cdots & *\\
0 & 0 & \cdots & 0 & * & \cdots & *\\
\vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 0 & * & \cdots & *
\end{array}\right).$$
So, now suppose that you have a basis for $\mathbf{V}$ that consists entirely of eigenvectors of $A$; let $\beta=[\mathbf{v}_1,\ldots,\mathbf{v}_n]$ be this basis, with $\mathbf{v}_1,\ldots,\mathbf{v}_{m_1}$ corresponding to $\lambda_1$ (with $m_1$ the algebraic multiplicity of $\lambda_1$, which equals the geometric multiplicity of $\lambda_1$); $\mathbf{v}_{m_1+1},\ldots,\mathbf{v}_{m_1+m_2}$ the eigenvectors corresponding to $\lambda_2$, and so on until we get to $\mathbf{v}_{m_1+\cdots+m_{k-1}+1},\ldots,\mathbf{v}_{m_1+\cdots+m_k}$ corresponding to $\lambda_k$. Note that $\mathbf{v}_{1},\ldots,\mathbf{v}_{m_1}$ are a basis for $E_{\lambda_1}$; that $\mathbf{v}_{m_1+1},\ldots,\mathbf{v}_{m_1+m_2}$ are a basis for $E_{\lambda_2}$, etc.
By what we just saw, each of $B\mathbf{v}_1,\ldots,B\mathbf{v}_{m_1}$ lies in $E_{\lambda_1}$, and so when we express it as a linear combination of vectors in $\beta$, the only vectors with nonzero coefficients are $\mathbf{v}_1,\ldots,\mathbf{v}_{m_1}$, because they are a basis for $E_{\lambda_1}$. So in the first $m_1$ columns of $[B]_{\beta}^{\beta}$ (the coordinate matrix of $B$ relative to $\beta$), the only nonzero entries in the first $m_1$ columns occur in the first $m_1$ rows.
Likewise, each of $B\mathbf{v}_{m_1+1},\ldots,B\mathbf{v}_{m_1+m_2}$ lies in $E_{\lambda_2}$, so when we express them as linear combinations of $\beta$, the only places where you can have nonzero coefficients are in the coefficients of $\mathbf{v}_{m_1+1},\ldots,\mathbf{v}_{m_1+m_2}$. So the $(m_1+1)$st through $(m_1+m_2)$st column of $[B]_{\beta}^{\beta}$ can only have nonzero entries in the $(m_1+1)$st through $(m_1+m_2)$st rows. And so on.
That means that $[B]_{\beta}^{\beta}$ is in fact block-diagonal, with the blocks corresponding to the eigenspaces $E_{\lambda_i}$ of $A$, exactly as described.
The given data does not determine the inner product $\newcommand{\ip}[2]{\langle#1,#2\rangle}\ip{\phi_j}{\phi_i'}$ when $i\neq j$ and $\lambda_i=\lambda_j$.
For a concrete example, let
$$
H(t)
=
\begin{pmatrix}
2t&t^2\\t^2&0
\end{pmatrix}.
$$
This has been chosen so that $H(0)=0$ is degenerate and $H'(0)$ is already diagonal.
The normalized eigenvector (unique up to sign) corresponding to the eigenvalue $t(1-\sqrt{1+t^2})$ is
$$
\frac1{\sqrt2}
\begin{pmatrix}
-\sqrt{1-\frac1{\sqrt{1+t^2}}}
\\
\sqrt{1+\frac1{\sqrt{1+t^2}}}
\end{pmatrix}.
$$
The lower component is $1+O(t^2)$ and the upper one is $t/2+O(t^3)$.
However, if you take $H(t)=\operatorname{diag}(2t,0)$, the data $H(0),H'(0)$ is the same and $\phi_i(0)$ are also unchanged.
However, $\phi_i'(0)$ does change: the eigenvectors are independent of $t$ now.
(The inner product $\ip{\phi_i}{\phi_i'}$ is zero in both cases, the only difference is in the direction orthogonal to $\phi_i$.)
The missing inner products depend on higher order derivatives of $H(t)$ at $t=0$.
The desired components can be found using second order perturbation theory, at least when $H'(0)$ is non-degenerate.
Take two distinct indices $i$ and $j$ so that $\lambda_i=\lambda_j$.
We also assume that $\lambda_i'\neq\lambda_j'$; this is the mentioned non-degeneracy assumption.
Using the observations in the question, we find $H'\phi_j=\lambda_j'\phi_j$.
This becomes useful once we differentiate (1) twice at $t=0$ and take an inner product with $\phi_j$.
We find
$$
\ip{\phi_j}{\phi_i'}
=
\frac{\ip{\phi_j}{H''\phi_i}}{2(\lambda_i'-\lambda_j')}.
$$
The details are left as an exercise.
If $H'$ is degenerate, I assume higher order derivatives are needed.
Best Answer
I think I solved it: If matrices $A$ and $S$ commute, i.e. $AS = SA$, then I eigenspaces of one matrix are invariant under the other matrix, because if $Ax = \lambda x$, then $A Sx = SAx = S\lambda x$, so if $x$ is eigenvector of $A$ with eigenvalue $\lambda$, then so is $S\lambda x$.
This in mind, I choose one of the matrices and diagonalize it, say I choose $S$. Then I get $S = T D T^\top$ with $T$ being unitary and $D$ being diagonal. If I then use $T$ to transform $A$, I get $A' = T A T^\top$ is block diagonal, because of the invariance mentioned earlier.
I can then diagonalize each block of $A$ on its own, because that way, the resulting eigenvectors of $A$ will remain eigenvectors of $S$. That way, I have simultaneously diagonalized $A$. The nice thing is that this can help make the resulting eigenvectors unique, because now eigenvectors are characterized not only by their $A$-matrix eigenvalue but also by their $S$-matrix eigenvalue.
If that doesn't suffice, I could search for more symmetries that all simultaneously commute with each other. An example from quantum mechanics is the hydrogen atom, where one find that the Hamiltonian commutes with the modulus of the angular momentum and its z-component, which ultimately gives rise to the three quantum numbers n, l and m.