Any linear map $C$ between two vector spaces ${\cal U}$ and ${\cal W}$ is uniquely defined as long as it is defined on a basis of ${\cal U}\,.$ A basis of ${\cal T}^r_s(V)$ is
$$\tag{1}
h_{i_1}\otimes\,...\,\otimes\,h_{i_r}\otimes \theta^{j_1}\,\otimes\,...\otimes\,\theta^{j_s}
$$
where all $i_k$ and all $j_l$ run through $\{1,...,n\}$ and
$\{h_1,...,h_n\}$ is a basis of $V$ and
$\{\theta_1,...\theta_n\}$ is a basis of $V^*\,.$ Unfortunately I do not have access to Newman's book but I strongly believe that he defines the map $C^k_l$ on a larger set than a basis of ${\cal T}^r_s(V)$ by allowing each of the factors $v_i$ and $\eta^j$ to be a linear combination of the basis vectors $h_\mu\,,$ resp. $\theta_\nu\,.$ (If his $v_i$ were all different, or his $\eta^j\,,$ this would not define $C^k_l$ on a basis of ${\cal T}^r_s(V)\,.$ Clearly, in (1) the factors are not all different.)
The only thing (if anything) that needs to be checked is if the contraction form of the right hand side of
\begin{align}
&C^k_l(v_1\otimes\ldots\otimes v_r\otimes\eta^1\otimes\ldots\otimes\eta^s)\\&=v_k(\eta^l)\,v_1\otimes\ldots\otimes \hat v_k\otimes\ldots\otimes v_r\otimes\eta^1\otimes\ldots\otimes\hat\eta^l\otimes\ldots\otimes\eta^s\tag{2}
\end{align}
is compatible with the same form for basis vectors:
\begin{align}
&C^k_l(h_{i_1}\otimes\,...\,\otimes\,h_{i_r}\otimes \theta^{j_1}\,\otimes\,...\otimes\,\theta^{j_s})\\&=h_{i_k}(\theta^{j_l})\,h_{i_1}\otimes\ldots\otimes \hat h_{i_k}\otimes\ldots\otimes h_{i_r}\otimes\theta^{j_1}\otimes\ldots\otimes\hat\theta^{j_l}\otimes\ldots\otimes\theta^{j_s}\,.\tag{3}
\end{align}
By linearity it is enough to expand only the hatted factors
$$
v_k=\alpha{^\mu}_k\,h_\mu\,,\quad\eta^l={\beta^l}_\nu\,\theta^\nu\quad\text{ (using summation convention) }
$$
and assume that in (2) the un-hatted factors are basis vectors. In other words we need to check that (3) implies
\begin{align}
&C^k_l(h_{i_1}\otimes\ldots\otimes v_k\otimes\ldots\otimes h_{i_r}\otimes\theta^{j_1}\otimes\ldots\otimes \eta^l\otimes\ldots\otimes\theta^{j_s})\\&=v_k(\eta^l)\,h_{i_1}\otimes\ldots\otimes \hat{v}_k\otimes\ldots\otimes h_{i_r}\otimes\theta^{j_1}\otimes\ldots\otimes \hat{\eta}^l\otimes\ldots\otimes\theta^{j_s}\,.\tag{2'}
\end{align}
From
$$
v_k(\eta^l)=\alpha{^\mu}_k{\beta^l}_\nu\,h_\mu(\theta^\nu)
$$
this should however by obvious. If not please note that $\mu,\nu$ are just dummy indices which we can replace:
$$
v_k(\eta^l)=\alpha{^{i_k}}_k{\beta^l}_{j_l}\,h_{i_k}(\theta^{j_l})\,.
$$
Interesting, in the newest edition of Lee's "Riemannian Manifolds" this is Proposition 2.40, and perhaps it gives a nicer hint. Let's get a few preliminaries down.
On a Riemannian manifold $M$ we have a metric $g$. The inner product is given as
$$
\langle X,Y\rangle=g_{ij}X^iY^j
$$
for $TM$ with respect to the coordinate frame.
Similarly, by considering the canonical bundle isomorphism $\tilde{g}:TM\to T^*M$ given by the Riemannian metric, we may construct a bundle metric on $T^*M$ as follows. For any $\eta,\xi\in T^*M$, there exists unique $X,Y\in TM$ such that
$$
\eta=g(X,\cdot),\;\;\xi=g(Y,\cdot),
$$
and we then define
$$
\langle\eta,\xi\rangle=\langle X,Y\rangle.
$$
We also have that
$$
\langle\eta,\xi\rangle=g^{ij}\eta_i\xi_j
$$
with respect to the coordinate frame.
Given a local orthonormal frame $(E_j)$ for $TM$, it may be checked that the dual frame $(\phi^i)$ is actually a local orthonormal frame for $T^*M$.
Now consider the tensor bundle $T^k_\ell(M)$ and define the bundle metric as follows. For any (pure) $(\ell,k)$-tensors
\begin{align*}
X_1\otimes\cdots\otimes X_\ell\otimes\eta^1\otimes\cdots\otimes\eta^k \\
Y_1\otimes\cdots\otimes Y_\ell\otimes\xi^1\otimes\cdots\otimes\xi^k
\end{align*}
in $T^k_\ell(M)$ we define
$$
\langle X_1\otimes\cdots\otimes X_\ell\otimes\eta^1\otimes\cdots\otimes\eta^k,Y_1\otimes\cdots\otimes Y_\ell\otimes\xi^1\otimes\cdots\otimes\xi^k\rangle=\langle X_1,Y_1\rangle\cdots\langle \eta^k,\xi^k\rangle.
$$
We then extend this bilinearly and this defines a bundle metric on $T^k_\ell(M)$. Note, this is in the statement of the proposition, and is what I consider the "hint".
With this definition, we may check that it satisfies your definition in coordinates, hence it is equivalent. Finally, by the statement above about the local orthonormal frames, and the "linearity over the tensor product", you should be able to check that the tensor products of basis elements determines a local orthonormal frame for the tensor bundle.
Best Answer
You're mixing up $k$ and $l$ several times. Also, where is it said that $b^i$ is both a covector and also a scalar component of the covector? It is just a covector! Its basis expansion is $b^i=b^i(e_j)\epsilon^j$, i.e the components of the covector $b^i$ relative to the basis $\{\epsilon^1,\dots,\epsilon^n\}$ of $V^*$ are the numbers $b^i(e_1),\dots, b^i(e_n)$, which if you feel so inclined, you can denote $b^i_{\,j}$.
Anyway, the basis for $T^k_l(V)=\underbrace{V^* \otimes \dots \otimes V^*}_{l} \otimes \underbrace{V \otimes \dots \otimes V}_{k}$ is given by the set \begin{align} B_{(k,l)}=\{\epsilon^{i_1}\otimes\cdots\otimes \epsilon^{i_l}\otimes e_{j_1}\otimes\cdots\otimes e_{j_k}\,|\,\, i_1,\dots, i_l,j_1,\dots, j_k\in\{1,\dots, n\}\}. \end{align} Note the ordering and the indices (the $l$ covectors appear in the tensor product first, followed by the $k$ vectors). Given any $F\in T^k_l(V)$, this can be thought of as a multilinear map $F:\underbrace{V^*\times \cdots \times V^*}_{k}\times\underbrace{V\times \dots \times V}_{l}\to\Bbb{R}$. Note the $k$ and $l$ and where the $*$ appears. The claim now is that \begin{align} F&=F(\epsilon^{j_1},\dots, \epsilon^{j_k},e_{i_1},\dots, e_{i_l})\cdot\epsilon^{i_1}\otimes \cdots\otimes\epsilon^{i_1}\otimes e_{j_1}\otimes\cdots\otimes e_{j_k}. \end{align}
Anyway, I would suggest first writing out the proof in a few special cases such as $(k,l)\in\{(1,0), (0,1), (1,1),(1,2),(2,1)\}$, because the general case is just a zillion more indices.