Generating an IV for ESP 3DES-CBC
To generate an IV securely for CBC mode, there are two obvious ways to do it (and both are cited by NIST):


For each packet, select a nonce (the IPSec sequence number, padded out to 64 bits, works fine), encrypt that in ECB mode, and then use resulting ciphertext block as the IV.  An equivalent way to do that is to take your 64 bit nonce, prepend that to the  byte plaintext, encrypt the plaintext (and the 64 bit nonce) with a fixed IV, and then transmit the first 64 bits of the ciphertext (not including the fixed IV you used) as the IV, and the rest of the ciphertext as the ciphertext body.  It turns out this is equivalent to the first method because of how CBC mode works internally.
For call a random number generator to select a 64 bit IV, and use that.  The text from NIST you cite says the rng has to be FIPS-approved; actually, unless you care about FIPS compliance, any unpredictable rng should work; I don't expect any problems /dev/random


Personally, I suspect you'll find the first option is easier.

The other thing you ought to consider is integrity; there's a surprising amount of mischief someone can cause by modifying the ciphertext, and then having someone attempt to decrypt it.  Now, IPSec has an answer to that (including a MAC along with the ciphertext; if someone modifies the ciphertext, the MAC will fail); are you including that?

BTW: the RFC you cite (RFC1851) is rather out-of-date, and won't interoperate with modern versions of IPSec; at the very least, modern versions will expect the padding to have a specific pattern.  That doesn't matter if you're implementing both sides of the protocol; however if the other side is a non-ancient IPSec implementation, look at RFC2406 and RFC2451