Let's say I attack David with Military. David opposes the challenge by putting out a single military character. Then I play a card that removes his military icon, like "The Prince's Wrath"- PotS. Is the challenge unopposed?

From the FAQ, pg. 22:

If my character loses a military icon in
the middle of a military challenge, is that
character removed from the challenge?

No. Once a character is in a challenge, it can
only be removed from that challenge by an
effect that specifically removes the character
from a challenge, an effect that removes
the character from play, or by an effect that
changes control of that character. Gaining or
losing icons mid-challenge does not affect the
attacking or defending status of that character.

Comes to this: you need an icon to be declared as an attacker or defender, but there is nothing in how you resolve a challenge that refers to icons. You do not need to have the appropriate icon to count your STR. And a character is only removed from a challenge if an effect specifically says so. Manipulating a character's icons after it has been declared in a challenge is effectively a waste of time (as far as that challenge goes).