If you really can't use an IV (why?), then just about the best thing you can do is use something like SIV mode (RFC 5297). SIV is a "maximally misuse-resistant" authenticated encryption mode which provides the following characteristics:
If every message is tagged with a unique nonce, SIV provides full IND-CCA2 security (up to the usual limits; i.e. it still leaks the length of the message).
Without a nonce, SIV remains IND-CCA2 secure as long as the same message is never encrypted twice (with the same associated data, if any).
If a message is encrypted twice without a nonce (or with an accidentally reused nonce), the only thing an attacker can learn is that those two messages are the same.
The down side of SIV mode is that it's a two-pass encryption mode: the encryption code must process the message twice. Thus, it is best suited for fairly short messages that can be held entirely in memory. Basically, on the first pass, SIV computes a secure message authentication code of the plaintext and any associated data (including the nonce, if provided); on the second pass, the message is encrypted using conventional CTR mode encryption, with the MAC from the first pass used as a "synthetic IV" (whence the name of the mode).
Also, to allow the message to be decrypted (and its authenticity verified), the 128-bit MAC/IV must be transmitted along with the message. Thus, SIV adds an unavoidable 16-byte overhead to each message, and is therefore not suited for format-preserving encryption. Of course, the same is true of every authenticated encryption mode, and indeed of every mode capable of providing semantic security, whether authenticated or not.
