To solve this problem, you will want to intelligently select a manageable set of combinations based on a pairwise coverage approach (explained below) or a more thorough variation of combinatorial test design.
Glowcoder and user246 have good points. I particularly like testerab's comment for reasons that will become clear in a minute.
I've created a relatively detailed sample plan to your specific problem and am making it available to anyone who would like to see it here: https://app.hexawise.com/share/JJNP37PJ (Apologies that registration is required to access it which is admittedly a bit of a nuisance; the good news is that registration is quick and free). You'll be able to edit my sample plan, replace my sample place-holder test inputs your actual test inputs, and quickly generate tests to solve your problem.
I have intensely studied test design problems like this one you've raised for the last 5 years. I have published articles and presentations about the benefits of the following approach to test design, collaborated with PhDs who specialize in maximally efficient test design, spoken at testing conferences extolling the benefits of this approach, and created the Hexawise test case design tool to make it easy for testers to automatically generate tests that solve for precisely the kinds of combinatorial explosions like the one you're talking about here. You could rightly say I've been obsessed with understanding this puzzle and trying to do my best to help others understand the most efficient and effective ways to address it. From my experiences and studies, this is what I would recommend:
Specific Solution (With Example)
First, you need to identify your test inputs. (I've borrowed a few ideas from glowcoder's answer) in my sample test plan's inputs in the plan shown here:
Once you've done that, click on the "Create Tests" button to create a set of pairwise tests. You'll see that there are 559,872 possible test cases. From those, Hexawise identifies the smallest possible set of tests it can create to ensure that every single possible pair of test inputs are tested together in at least one test case. Believe it or not, it takes only 22 tests do do so. Technically, every single pair of test inputs appears except for one pair of values. The missing pair was intentionally removed from the solution because it would have been impossible for a tester to execute; the Invalid Pair that does not appear in the solution is O/S = Mac OSX tested together with Browser = IE.
If you click on the "Analyze Tests" feature, it will take you to a screen that will make you happy based on your question. It will show what percentage of those combinations have been covered at each point in your test plan. After just ten tests, 76.2% of the potential pairs of values that exist in the System Under Test will already have been tested together in at least one test case.
Those first ten tests will find a large percentage of the bugs in the System Under Test (and the 22 may well find a few additional ones). From there, the marginal return on your tests will fall significantly for the simple reason that defects that can only be triggered by specific combinations of 3 or more variables are quite rare. This chart shows the specific coverage gaps that would exist if you stopped executing tests after your first 13 tests:
Having said that, if you'd like to achieve more thorough coverage than those unusually powerful initial 22 tests, that is easily achievable as well. You can select "3-way" coverage on the drop down menu on the Create Tests screen. You'll find that only 95 tests are required to test for every single possible combination of 3 values that are in the plan. (4-way coverage would require 359 tests, etc. The point is, you can turn the coverage dial up or down to meet your thoroughness objectives).
Some good, succinct information about pairwise test design methods, combinatorial testing, the Hexawise tool, Design of Experiments-based software test design methods, and orthogonal array (AKA OA or OATS)-based test design methods can be found in the links cited here (<---- informational links including articles, and an amusing and insightful set of pohtograph-rich, introductory PowerPoint slides.)
I hope this answer helps.