Yes, the constitution allows pardoning people who haven't been charged.
Reduction of a sentence is not technically considered pardoning. A President can pardon someone who hasn't be charged. Pardons make an individual immune to any conviction in future.
Article 2, Section 3, Clause 1 of the U.S. Constitution gives the President the right to pardon:
[The President] shall have Power to grant Reprieves and Pardons for Offences against the United States, except in Cases of Impeachment.
An example is Gerald Ford pardoning Richard Nixon after Nixon resigned. The pardon absolved the former president of "all offenses against the United States which he … has committed or may have committed or taken part in" between the date of his inauguration in 1969 and his resignation in August 1974.
This Slate article further describes why people not charged can be pardoned.
Snowden can actually be pardoned, Obama may have meant that he "won't" pardon Snowden rather than "can't" pardon. So, the pardon means that he won't be charged for all offences he may have committed.