1: Use a friends computer that you know is secure (I would still be suspect of your machine right now)
2: Go to http://www.pctools.com/guides/password/ and generate 10x (or more) 12 digit passwords with all options checked
3: Register a completely new gmail account, use the first of the new passwords (this will be your new recovery account), for the security question choose "my own question" put anything you like there but use the 2nd password you generated for the answer.
4: Enable two step verification for your google account (sms code), this means people can't login unless they have a sms code sent to your phone. Never check "stay signed in" for this account, always click "sign out" for this account rather than just closing the browser.
5: Recover your existing accounts (starting first with email accounts that are set as the recovery for other accounts) however you can. Use two of the generated passwords for each account, one as the new password the 2nd as the new security answer.
Update the secondary or recovery email address to your new gmail account if the service allows this.
Once you've done this get an expert to look at your computer and check for rootkits and malware.