2) Reduced the keyword density on 10 pages out of 300
3) Reduced internal links(related pages links)
For the same keywords for which I was de-indexed, now pages are being shown on the first page and some with improved rankings(probably because some competitors got hammered and they haven't made the corrections)
There are ~200 spammy backlinks purchased from Fiverr, hoping they will go away or ignored by Google.
I am also planning to use some CDN service like cloudfront to further improve page loading time.