How Bitcoin wallets avoid address re-usability?
Is wallet generates an address from index 1 and scan blockchain whether an address is used or not, until wallet finds an unspent address?


No. The wallet software generates a seed (pseudo-random). With that seed, it generates private keys. With those private keys, it generates public keys and with those public keys, it generates addresses. And this address is (almost) always unused.


  and checks whether the index is used or not until it reaches address that has not been used.
  ---- and ----
  If the wallet is stateless, then determining unused address by generating the address from very first and looking up blockchain for the unused address is expensive?


That's not how it works. The probability to hit an address that is already used (by the method seed->SK->PK->address) is almost 0 because you don't know the seed of other people. You don't need to check that because it's almost impossible (unless you have a lot of computer power and want to waste electricity).


  Is the wallet keeps state of unused address?


The wallet simply check the funds of all your addresses, recognizes that your first address is used (has funds on it) and provides you a new one (also created by the same seed (seed->SK->PK->address).