There is a local computer store that takes in computers for in-store credit where I live. I don't know of any online store that trades / buys for in-store credit. I would scan yellowpages.com for your local computer shops (if you have any), and see what they can do for you.
If you would build your own computer, is there anything you would salvage from your current computer? ex: case, motherboard, HDD. Also, would you need to buy an OS? An $800 limit for a completely new computer is not much, but it will be able to play every game on the market. You just will not be able to max out some games.