Does a Message authentication code (MAC) ensure authenticity of the key used?

I have to protects confidentiality, integrity and authenticity of a file of records with a password. The number of records can potentially be more then 32^2 and each record can be accessed independently.

One way to implement it is

1. Generate a 256-bit random salt and store it in the file header.
2. Generate a derived key from the password and the salt using PBKDF2 with HMAC-SHA256 from PKCS #5.
3. For each record generate a 96-bit random initialization vector.
4. Encrypt each record's content using AES-256 in GCM mode using the derived key, the initialization vector, and (as additional authenticated data) the position of the record in a file.
5. As a result, each record will store an initialization vector, an encrypted content, and a MAC.

But the NIST Special Publication SP800-38D defining GCM and GMAC requires the number of records to be less than 32^2 for the initialization vectors to be unique.

So I devised another solution: create a key for each record with HMAC-SHA256 using the derived key as a key and the position of the record in a file as a message to be authenticated (salt).

So the question is do I need to provide the position of the record in a file to the authenticated encryption algorithm as an additional authenticated data since I've already taken care of it when generating the key?

Additionally do I really need to use initialization vectors at all since all the records will be encrypted and authenticated using supposedly different keys generated by HMAC-SHA256(PBKDF2(HMAC-SHA256, password, salt, iterationCount, 256), blockAddress) ?

I don't know what the size of the file will be, so I presume it can be very large.

If I understood you correctly (bit of a disclaimer, sorry) then you should be fine without adding the position within the record in the file.

No you don't need a random IV if you only use a (session) key once. Using an IV consisting of zero's would be enough (deterministic construction, using one device and a counter set to zero, if we keep with the NIST nomenclature).