Deriving the solution from the useless symbols elimination algorithm.
There are several aspects to this algorithm. For better intuition I chose to present it in three successive version that introduce progressively more features. The first version does not answer the question, but is a standard algorithms that suggests a solution.
The basic algorithm
To solve this question, one can start with the classical algorithm for useless symbols removal in context-free grammars. It is in section 4.4, pp 88-89, of Hopcroft & Ullman, 1979 edition. But the presentation here may be a bit different.
The algorithm aims precisely at proving the existence of such a covering as requested by the OP, and consists in two parts:
lemma 4.1 of H&U, page 88: removal of all unproductive terminals. This is done by trying find for each terminal a terminal string it can derive on. A simple way to explain it is as follow: You create a set $Prod$ od productive symbols, which you initialize with all terminals. Then for each rule, not yet processed, that has all its right-hand-side (RHS) symbols in $Prod$, you add the left-hand-side (LHS) non-terminal to the set $Prod$ (in the original algorithm, you only have to consider rule with a LHS symbol not yet in $Prod$). You iterate the process until there is no rule left with all its RHS symbols in $Prod$. The LHS symbols of all remaining rules are non-productive (cannot be derived into a terminal string) and can thus be removed from the grammar.
lemma 4.2 of H&U, page 89: removal of all unreachable symbols. This is done by the classical node reachability in directed graphs, by considering non-terminals as nodes and having an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha$ such that $V$ occurs in $\alpha$. You create a set $Reach$ of reachable symbols which is initialized with only the initial symbol $S$. Then, for every non-terminal symbol $U$ in $Reach$ or later added to it, and for every rule $U\rightarrow \alpha$, you add to $Reach$ all the symbols in $\alpha$. When all non-terminals in $Reach$ have been thus processed, all symbols (terminal or non-terminals) that are not included in $Reach$ cannot appear in a string derived from the initial symbol, and are therefore useless. Thus they can be removed from the grammar.
These two basic algorithms are useful to simplify the raw results of some grammar construction techniques, such as used for the intersection of a context-free language and a regular set. In particular, this is useful in cleaning up the results of general CF parsers.
Useless non-terminal symbols removal is necessary in the context of solving the question asked, as the rules using them cannot be "invoked" (i.e. used in its derivation) by any string of the language.
Building a set of string that invoke all rules
(We are not looking yet for minimal strings.)
Now answering specifically the question, one must indeed remove all useless symbols, whether unreachable symbols or unproductive non-terminal symbols, a well as rules having such useless non-terminals as LHS. They have no chance of being ever invoked usefully while parsing a terminal string (though some may well waste the processing time of a parser when they are not removed; which ones may waste time depends on the parser technology).
Regarding the production of a covering by terminal strings that invoke all (useful) rules, this is essentially what is done by these two algorithms, though they do not keep the information, if in the first one (lemma 4.1) all rules are used rather than only those that do not yet have their LHS in the $Prod$ set. Only existence has to be proved by the original algorithms.
We modify the first algorithm (lemma 4.1) by keeping with each non-terminal $U$ in the set $Prod$ a terminal string $\sigma(U)$ it derives on: $U\overset{*}{\Longrightarrow}\sigma(U)$. For every terminal (used to initialize the set $Prod$) we define the $\sigma$ as the identity mapping. When $U$ is added to the set $Prod$ because a rule $U\rightarrow\gamma$ has all its RHS symbols in $Prod$, then we define $\sigma(U)=\sigma(\gamma)$, extending $\sigma$ as a homomorphism on strings.
We modify the second algorithm (lemma 4.2) by keeping with each non-terminal symbol $U$ added to $Reach$ the path used to reach it from the intial symbol $S$, which gives the successive rules to get a derivation $S\overset{*}{\Longrightarrow}\alpha U \beta$.
Then, for each rule $U\rightarrow\gamma$ in the grammar, we produce a terminal string that "invokes" this rule as follows. We take from the result of the second algorithm the derivation $S\overset{*}{\Longrightarrow}\alpha U \beta$. Then we apply the rule to get the string $\alpha \gamma \beta$. A terminal string "invoking" the rule $U\rightarrow\gamma$ is $\sigma(\alpha \gamma \beta)$
Building a set of minimal strings that "invoke" every rule
We ignore the issue of eliminating useless symbols, which can be a by-product of these modified algorithms.
Building a set of minimal strings relies on first getting a minimal derived string for each nom-terminal. This is done by further modifying the first algorithm (lemma 4.1). First we remove from the set of rules to be processed all recursive rules (i.e. with a LHS symbol occurring in the RHS string). It is obvious that none of these rules can derive to a shorter terminal string than the non-recursive rules with the same LHS. And there must be at least one non-recursive rule if the LHS is not a useless non-terminal (because non-productive).
Then we procede as before to build the set $Prod$ of productive symbols, associating with each synbol $U$ a terminal string, which we note $\sigma(U)$. The string $\sigma(U)$ is produced as before by application of the rule $U\rightarrow\gamma$, substituting each non-terminal $V$ occurring in $\gamma$ with $\sigma(V)$. So far, it was necessary to apply this to only one rule with a given non-terminal $U$ as its LHS, the first that would have all its RHS non-terminals in $Prod$, and then ignore the others, because any such derived string would do. But we are now looking for a minimal derived string. Hence, for a non-terminal $U$, this has to be done for all rules with $U$ as LHS. But we keep only one terminal string $\sigma(U)$, replacing the current one by the newly found one, whenever the new one is smaller.
Furthermore, whenever the string $\sigma(U)$ is replaced by a smaller one, all rules with an occurrence of $U$ in the RHS that had been already processed have to be put back in the set of rules to be processed, since change allows deriving their RHS on a shorter string. So doing this will call for more iterations, but will eventually end since none of these strings ever gets much shorter than the empty string.
At the end of this first algorithm, the string $\sigma(U)$ is one of the smallest strings that can be derived from $U$. There may be others.
Now we also have to modify the second algorithm to get, for every non-terminal $U$, (one of) the shortest string containing U as the only non-terminal. To do this, we keep the same directed graph with non-terminals as nodes, and having an arc $(U,V)$ iff there is a rule $U\rightarrow \alpha V \beta$. But now we put weights on the arcs, to compute the minimum length of the terminal context that has to be associated with reachable non-terminals. The weight associated with the arc $(U,V)$ above is the length $|\sigma(\alpha\beta)|$, where the mapping $\sigma$ is extended to terminals as the identity, and then extended again as a string homomorphism. It is the length of (one of) the shortest terminal strings that can be derived from the string $\alpha\beta$. Note that $V$ is removed in this calculation. HOwever, when there are several occurences of $V$ in the RHS, only one must be removed. There may be several possible $(U,V)$ arcs, with different weights, if there are several rules with $U$ as LHS and $V$ in the RHS. In such a case, only (one of) the lighter such arc is kept.
In this graph, we no longer look just for reachability of nodes from $S$, but for the shortest weighted path that reaches every node from the initial symbol $S$. This can be done with Dijkstra's algorithm.
Given the shortest path for a non-terminal $U$, we read it as before as a sequence of rules, from which we get a dérivation $S\overset{*}{\Longrightarrow}\alpha U \beta$. Then to every rule of the form $U\rightarrow\gamma$ in the grammar, we produce a minimal terminal string that "invokes" this rule as $\sigma(\alpha\gamma\beta)$
The same minimal string may probably be used for several rules. But the fact that one of the strings uses a rule $\rho$ in its derivation does not necessarily mean it is a minimal string for that rule $\rho$, as it may have been found for another rule, while a shorter one can be found for $\rho$.
Note that the fact that a string "invokes" a rule does not necessarily means that the rule will be considered by a parser that work with ambiguous grammars and resolves ambiguities arbitrarily.