A simple observation is that when an object is assigned an id, that id never increases, i.e., it either stays the same or decreases. So keep a global counter $g$ for giving ids, initially set to 0.
Let $A$ be your list of indices (or objects). Consider a deletion event $D$ consisting of ids you want to delete. To reindex, scan $A$ starting from the 0th index. Whenever $i \in D$, delete the corresponding entry in $A$ and increment a counter, say $d$, initially set to zero. For each subsequent index $j > i$, decrement each entry by $d$ (again, if you encounter an index you must delete, you decrement $d$ etc.).
So let me describe the basic idea with $A = [0,1,\ldots,9]$. Let $D = [2,4]$. Scan $A$, and at $i = 2$ set $d = 1$ and $A = [0,1,x,3,4,5,6,7,8,9]$. Continuing from $i=3$, we get $A=[0,1,x,2,4,5,6,7,8,9]$. Next, at $i = 4$, we mark $A[i]$ deleted and get $d = 2$. Thus, we are left with $A=[0,1,x,2,x,3,4,5,6,7]$. As $d = 2$, we update $g$ to $g - d$.
We can implement the above by looping over the elements in $D$. If $i'$ is the index in $D$, mark $A[i'] = x$, increment $d$ by one, and scan $A$ until $j' > i'$ where $j'$ is the next index in $D$ (or if there is no $j'$, scan until the end of $A$), and decrement each element of $A$ by $d$. You can implement this scheme to run in $\Theta(n)$ time, where $n$ is the number of elements in $A$. Indeed, we scan over $D$ once (and note that $|D| \leq |A|$ as it only contains indices to $A$) and also scan over $A$ once, essentially only skipping as many elements from the beginning of $A$ as the first index $i'$ in $D$ lets us. Finally, as $g$ is always kept up to date, you can generate new ids in $O(1)$ time too.
So with this implementation, the above example becomes as follows. Loop over $D$, i.e., start at $i' = 2$. Mark $A[i'] = x$. Check that $j' = 4$, so decrement $A[3]$ by one and mark $A[j'] = x$. Now, we see that there is no $j'' > j'$, so decrement each $A[\ell]$ by two, for $j' + 1 \leq \ell \leq n$. Set $g := g - 2$ and halt.
