AES encryption with shared IV Sorry about the horrible title, didn't now what to say.

I'm trying to avoid having to send an IV with every message purely to keep packet sizes down, so I thought of a method to establish a "IV Pool".

This is how I thought it should be:

Client ---- Handshake ---> Server

Server ---- Handshake ---> Client

Client and Server now have a shared 1024-bit secret

First 256-bit's of the key are used as AES Key.

Now what I thought is, could I take the next 128-bits of the secret as the IV for the first encryption, and then send a massive list of random bytes to the server to use as IV's? For example:

Client ---- Sends 1024 bytes of random ---> Server

Then the client and server both take 128-bits of the random bytes each time they send a message as the IV. That way the IV is synced across both parties and the IV does not change and is theoretically "not-predictable".

My question is, is this safe? Or does it still defeat the purpose of having an IV?
Sending a big block of data to be then used as initialization vectors is secure (assuming it is transferred encrypted and authenticated), but kind of defeats the purpose of "keeping the message size down".

The requirements for an initialization vector depend on the mode of operation, not on the underlying cipher (AES in your case).

For CBC mode, the initialization vector for each message should be at least not predictable by an attacker before the message is known (otherwise there are some chosen-plaintext attacks which allow decrypting your message).
Old versions of SSL used the last block of the previous message, and were thus vulnerable to this attack – newer versions send an IV with each message.

One way to go here would be to use part of your 1024 bit shared secret as the seed for a CSPRNG (on both sides), and use the output of this as IVs. (Use separate generators for both directions.)

For CTR mode, the initialization vector can either be random (see above), or be simply counted up from the last counter value of the last package, and if this is decided in the protocol, you don't need to send it along with the message. 

(Of course, in both cases this only holds if your messages are protected from reordering by some other mechanism – e.g. if this is done over TCP.)

Your MAC (you have a MAC, don't you?) should include the initialization vector, even if it is not sent.

There are other modes of operation, including most AEAD modes, which only require the nonce-property of the initialization vector, i.e. that it is not repeated. Then you can use a simple counter, or use an existing message number (maybe together with an identifier of the sending side).

Also note that the streams in both directions should use different keys, not the same one.