For GCM, IV can be predictable (contrary to some other modes such as CBC, there is no unpredictability or uniformness requirement), but they must not be reused. You are free to use any method you wish to ensure this uniqueness. If an IV is reused, then the "authentication key" is revealed, and the encryption itself becomes an instance of the "two-times pad", i.e. may leak a lot of information on the plaintext, depending on its format.
A timestamp is sort-of fine. The problem with timestamps is that they depend on a local clock, and since there is no such thing as a perfect clock, computers routinely include ways to adjust clocks, either manually or automatically. Note that automatic clock adjustment over the Internet uses NTP, which is usually unprotected (no authentication or encryption). Therefore, remote attackers may feed a connected system with fake NTP packets to force a clock adjustment and possibly an IV reuse.
Using a random value is a common way to achieve uniqueness with a high probability; with 96-bit IV, if you encrypt no more than $2^{32}$ messages with a given key, then probability of an IV collision (assuming a strong random source) will be at most $2^{-32}$, which is low enough to deter attackers (i.e. it's less worthwhile to wait for such an event than to simply buy lottery tickets).
Some extra notes:
GCM actually supports all IV lengths, not just "12 bytes". An IV with length exactly 12 bytes is used "as is" and lets you know exactly if you have a collision or not. If you use a 64-bit timestamp (assumed non-repeating), you are encouraged to "pad it" with 4 extra bytes (e.g. zeros) so that the GCM implementation receives a 12-byte IV (even if you do not actually transmit the padding bytes in the message on the wire).
Conversely, you could use a longer random IV. 16-byte random IV are arguably "better" than 12-byte random IV (it makes risks of collisions lower as long as individual messages are substantially shorter than 64 gigabytes, and collisions are less immediately detectable by attackers). But since you try to reduce on-wire size, I suppose you'd prefer not to do that.
In some contexts, you can get a non-repeating IV "for free". E.g., in a TLS connection, each connection has its own key, so that IV collisions matter only within a given connection. But then, messages ("records" in TLS terminology) are successive; thus, a simple sequence number can be used (first record gets number 0, second record gets number 1, and so on). The sequence number is implicit and thus needs not be transmitted at all.
There may be other solutions. For instance, a possible method would be to replace GCM with the following mode:
- Let x be the IV (see below for its length) and m the plaintext to encrypt.
- Compute HMAC/SHA-256 over the concatenation of the IV and the plaintext, and truncate it to the AES block size (16 bytes). This yields the authentication tag t.
- Use AES-CTR encryption over m with t as IV; this yields the ciphertext m'.
- Transmit x, t and m'.
With such a mechanism, you could use a very short IV x, even an empty one (of length 0). Note that this saves space, compared to GCM: with GCM, the encrypted message is sent along with an authentication tag (16 bytes) and an IV; here, I suggest use the HMAC-derived authentication tag as IV for encryption.
If you use that kind of mechanism with an empty IV x, then the whole thing becomes deterministic: if you encrypt twice the exact same message with the same key, then you get the exact same encrypted message. However, this should be the full extent of the leak. A small but non-empty IV x can help in hiding that.
Note that this is an encrypt-and-MAC setup, usually frowned upon for theoretical reasons. It is reasonably safe in this case, because HMAC/SHA-256 also protects confidentiality of the input (this is not necessarily the case of any other MAC mechanism), and CTR decryption implies no padding, and thus can be safely implemented even over unvalidated input data.
Summary: if your timestamp are really unique, then they are enough for GCM, and you can pad them to 12 bytes with zeros (that need not be transmitted along with the message). However, if clocks can be adjusted or rewinded, then you should probably use random IV instead, to get "probabilistic uniqueness"; and, in that case, don't go lower than 12 bytes. If you are desperate for size, then there are other possible avenues, but they are outside of existing published standards, which means that you need more external review and development care.
