How can I create 10-character, unique codes with no collisions, but without being predictable? If we are using numbers and letters, there are $36^{10}$ unique combinations. Collision is already unlikely, but I need it to be impossible, so using hashing is out of the picture(?).

The use-case is users redeeming each one if they have been "activated" as redeemable. Think like Webkinz codes.

An inefficient solution would be to generate all of them at once, have a property on each saying whether it has been activated or not and keep a pool of those that have been redeemed and those that haven't.

Keeping a database of $36^{10}$ codes just because I can't come up with a clever algorithm is pissing me off, so I'm here for your help. 

Any ideas?
$36^{10}$ is approximately 52-bit. Now;

Generate a secret key $k$ for AES-128
Encrypt the rowID with $\text{unique_code} = \operatorname{AES}_k(rowID)$, and assuming that the key never changes.

Since AES with a key selects permutation for all possible permutations from $2^{\ell}$ to $2^{\ell}$, where $\ell$ with a key, then by fixing a key, you fixed a secret permutation. Therefore the output is distinct for every distinct input. It is unpredictable since AES is assumed to be secure against Known-Plaintext Attacks.