What is best to use (for message integrity) between…
- AES(Data) + HMAC(Data)
- AES(Data + HMAC(Data))
- AES(Data + Hash(Data))
2, because the only issue is that there might be a feasible way to have a non-negligible
(Of course, as pointed to by hunter, AES(data) + HMAC(AES(data)) is even better.)
"Encrypted hash" totally fails if the encryption uses a malleable mode like CTR. CTR runs AES in a stream-cipher-like mode where the data to encrypt is simply XORed with a key-dependent stream, so the attacker can flip bits with extreme precision; so if the attacker guesses the contents, he can modify them and fix the hash easily.
More generally, if you want a MAC then use a MAC. The "encrypted hash" is just a homemade attempt at a MAC algorithm, and we know that homemade algorithms are rarely strong, and even when they are we cannot make sure that they really are strong.
As for how to combine encryption and a MAC, this is a well-known questions for which a lot of theory and practice has been accumulated; see this question. To sum it up: you want to compute the MAC over the encrypted data, because it avoids any issue with the MAC algorithm leaking information on the processed data, and it protects the decryption implementation from malformed data.
Now, HMAC seems to be reasonably well-behaved and not to leak information about the data on which it is applied. Your setups 1 and 2 are what is used by, respectively, SSH and SSL/TLS. In neither case did it prove fatal; however, the lack of protection on the encrypted format allowed various padding oracle attacks to experience some success on implementations which were not sufficiently careful when decrypting malformed input data.