I think you need to be a little careful here with the calculations.

For (mod 8), $11\equiv 3\pmod{8}$, so aren't all the even powers $\equiv 1\pmod{8}$, not the odd ones?

As a hint for the (mod 125) portion. By Euler's Totient Function ($\phi(125) = 100$), $11^{100}\equiv 1 \pmod{125}$ so we are left with $11^{11}\pmod{125}$. This isn't too bad to "bash" out. Hint: $11^2\equiv -4 \pmod{125}$.

Then as you mentioned, you need to put these two together to find the answer (mod 1000).

To see the spoiled answer (remember we just want the hundreds digit) click here for the calculation on Wolfram Alpha.