For the 39 non-hearts, define $A_i,\, 1\leq i\leq 39 $ to be the event that card $i$
appears before all the hearts. The number of draws until we get the first heart is
$X=1+\sum_{i=1}^{39} 1_{A_i}$, and since $\mathbb{P}(A_i)=1/14$ we get
$$\mbox{average number of draws}
=\mathbb{E}(X)=1+\sum_i \mathbb{P}(A_i)=53/14\approx 3.79.$$
You don't specify an initial state. From your result for $A$, I infer that you're interested in the expected score in equilibrium (which is $\frac14$ per draw in $A$), not starting from a full deck (which would be slightly different).
In the general case, in a shuffled deck the $i+j$ non-reshuffle cards are equidistributed over the $k+1$ intervals formed by the $k$ reshuffle cards. Thus, on average we draw $\frac{i+j}{k+1}$ non-reshuffle cards before drawing a reshuffle card, and the expected score from these is $\frac i{k+1}$. Thus the expected score per draw is
$$
\frac{\frac i{k+1}}{\frac{i+j}{k+1}+1}=\frac i{i+j+k+1}
$$
(where $+1$ counts the reshuffle card). In your two specific cases, this yields
$$
\frac1{1+0+2+1}=\frac14
$$
and
$$
\frac1{1+10+2+1}=\frac1{14}\;,
$$
respectively.
Note that interestingly it doesn't matter how many of the non-scoring cards are zeros or reshuffles. As long as there's at least one reshuffle card, the expected score per draw is simply $\frac i{n+1}$, where $n$ is the total number of cards, compared to $\frac in$ if you loop through a deck without reshuffle cards.
Edit in response to a comment:
The ratio $\frac{\frac i{k+1}}{\frac{i+j}{k+1}+1}$ comes about as follows: Each time we draw from a full, shuffled deck up to and including a reshuffle card, the expected score is $\frac i{k+1}$ and the expected number of draws is $\frac{i+j}{k+1}+1$. For one such run, the expectation of the score per draw is hard to determine; it isn't simply the ratio of the two expectations. For instance, in your first example, we score $0/1$ with probability $\frac23$ and $1/2$ with probability $\frac13$, so the expectation of the score per draw is $\frac23\cdot0+\frac13\cdot\frac12=\frac16\ne\frac14$. However, if we perform a very large number $m$ of such runs, the number of draws will be close to $m$ times the expected number of draws per run, and the score will be close to $m$ times the expected score per run, so for all the runs together, the expectation of the score per draw is simply the ratio between the expected score per run and the expected number of draws per run.
Best Answer
Visualize the 26 red cards and the 27 "gaps" between them. You want the expected number of black cards in the first four gaps (before the 4th red card), and then you need to add 4 (since you need to count the first 4 red cards).
Each black card is equally likely ($1/27$) to be in any of the 27 gaps between the red cards. In particular, the probability of a black card being in the first four gaps is $4/27$. Thus, the expected number of black cards in the first four gaps is $26 \cdot \frac{4}{27}$.
Then, add $4$ to account for the red cards.