A Google Books search finds two instances of "minutes and counting" (and "seconds and counting" from the same articles)—but nothing earlier. From "Countdown!" in Popular Mechanics Magazine (July 1958), describing the test launch of "a mighty Atlas" intercontinental ballistic missile:
With the new supply of oxygen delivered and the trucks safely out of the area the count resumes: "T minus 36 minutes and counting." Nearly two hours have been lost. Again liquid oxygen is pumped into the missile.
"T minus 10 minutes and counting."
The test conductor receives new reports on the weather, range instrumentation and range safety.
"T minus four minutes and counting."
A flow of water is started over the flame deflector to preserve it from the blast of the rocket engines.
"T minus 40 seconds and counting."
The level of liquid oxygen is checked and adjusted if necessary.
"T minus 35 seconds and counting."
Telemetering recorders are turned on.
"T minus 27 seconds and counting."
Automatic cameras around the stand begin operating.
"T minus 10 seconds and counting."
"Nine, eight, seven ..."
Another set of cameras starts.
"Six, five, four ..."
The vernier engines start.
"Three, two, on."
The last set of cameras starts.
Silence in the blockhouse is broken by the simultaneous cry of "mainstage" from the two periscope officers.
We have lift-off.
And from Aviation Week and Space Technology, volume 68 (1958), coverage of a similar countdown—or perhaps an independent account of the same one [combined snippets]:
• At T-minus-60 sec., test conductor announces "T minus 60 seconds and counting." Range safety command devices (engine cutoff and missile destruct explosives) armed.
• At T-minus-50 sec., pad safety officer reports the range is ready for firing.
• At T-minus-45 sec., test conductor makes these checks, panel operators respond. "Range safety armed light on— Roger." "Range ready— Roger." "Water system ready— Roger." "Preparation complete light— Green." "Liquid oxygen tanking secured— Roger."
...and so on. You can almost hear Slim Pickens (in Dr. Strangelove) intoning "one hundred dollars in rubles; one hundred dollars in gold; nine packs of chewing gum; one issue of prophylactics ..."
Anyway, it seems clear that Brian Donovan is correct in attributing the "and counting" catchphrase to the U.S. government's space and rocketry programs—although the phrase is slightly older than the National Aeronautics and Space Administration (NASA), which Wikipedia says took over from the older National Advisory Committee for Aeronautics (NACA) on October 1, 1958. It's also interesting that in its original form "and counting" meant "and counting down toward zero," whereas today the phrase frequently occurs in settings (such as the one in New York Times article) where the count is going up toward an indefinitely higher number.