How to retrieve reset bit in constant time in a bit array
Access into a bit array is constant time.  In particular, if you have an array that is stored contiguously in memory, indexing into the array takes constant time: reading $A[i]$ takes constant time, regardless of how large $i$ is.  That's all that you need to do to access a bit array.  In particular, if you have an array of bytes, then you can read the $i$th bit of the bit-array by reading $A[i/8]$ and doing a bit-masking operation to get the $(i \bmod 8)$th bit of that byte, and so on.

If you want to find a new session id that is not in use, that can be done in (expected) constant time as long as at least 1/2 of the session ids are not in use.  You simply pick a random session id, check whether it is in use, and repeat until you find one that is not in use.  If at least 1/2 of the session ids are not in use, the expected number of times you need to repeat this until you find one that is not in use is 2 (as it's expected the number of coin tosses until you get a heads, which is a geometric series), i.e., a constant.  Each iteration takes constant time, so the whole thing can be done in $O(1)$ time.

So, a bit array already meets all of your requirements. Just make sure that at least 1/2 of the session ids are not in use.

(What do you do if more than 1/2 of the session ids are in use?  Double the size of the array, copying over the old array if needed.  The doubling will happen rarely enough that the amortized time for each operation remains constant, i.e., $O(1)$.)