I'm not clear on if you want the cheapest "computer" possible or the cheapest laptop possible or the cheapest desktop possible.
The cheapest functional computer possible is probably something along the lines of a Picotux: http://www.picotux.com/ (99 EU for the 2MB version). There are very specialized versions of Linux (such as minix, or some BSDs) that can run entirely from a floppy (1.44MB), so 2MB of flash RAM is plenty of room.
Oh, but you mentioned you wanted 4GB of RAM, and 1.44MB is only 0.00036% of that, so I'm going to assume you really want the cheapest desktop or laptop available.
The cheapest of both is always free. RE-PC (or one of the several other electronic recycling places with a retail store in the Seattle area) won't give you stuff for free, but the people who give them stuff for free (or even pay them to come pick it up and get rid of it!) will.
You have to find those people. Since I manage a large-ish amount of computers, I am occasionally one of those people and have given away dozens (hundreds?) of things that were put up for grabs before eventually ending up at RE-PC. Everything from USB cables to hard drives to monitors to desktops to (really old) laptops. Even a couple Macs! Unfortunately, right now the closets are clear at work and I don't really have anything for you. But someone out there might!
Second to free, RE-PC (and similar stores, there is another one literally across the street) are worth checking out and do sell used, bare-bones machines, but to be totally honest I have always felt their prices are too high for me when I'm at RE-PC and feeling cheap.
You could try to find a decent deal on craigslist (try not to get robbed), or maybe the QuestionLand marketplace, but there is a large demand for cheap/free computers that don't suck so I wouldn't expect a miracle.
If you're going to buy a new laptop, my first advice is to see if you can afford a used Macbook. They start brand new at like $899 (I think) so you may find one 4-5 years old that is in your price range. Macbooks are the best laptops in existence and anyone who disagrees is simply wrong.
As far as PC laptops go, netbooks are cheaper than laptops (especially since their market is disappearing to tablets), but they are also not very high quality. I've seen a lot of people blow through a lot of netbooks from all different makes. You can find netbooks as cheap as $199, but with 4GB of RAM you're in "good netbook" to "crappy laptop" territory (aka $400-500). I have no strong opinions on good PC laptops but I have seen Dells, Lenovos, HPs, and Sonys that seemed okay in the last year.
PC desktops are much more interesting to build cheaply because you can build them part-by-part if you know how to build a computer, which really isn't very hard. There are lots of videos and articles online that take you through parting out a computer to purchase and build on Newegg. Only shop at Newegg or Amazon Prime -- every other site sucks for computer hardware (unless you need any sort of cable, then you go to monoprice.com).
Since Newegg rules, they have a whole category of "bare bone" computers of varying levels of bareness. Here are all of them sorted by price: http://www.newegg.com/Store/SubCategory.aspx?SubCategory=3&name=Barebone-Systems&Order=PRICE
At the end of the day your average "cheap but decent" (as you described) netbook should cost around $300, laptop around $500, and desktop (without monitor) probably closer to $400. Keep in mind Windows 7 costs $100 bare-minimum unless you pirate it or use a free OS (I'd try out Ubuntu). Reduce all prices by 20-30% if you go for used.
I'd buy a used 3-5 year old Macbook for $400-600.
Some people nerd out and try to build the cheapest functional computer possible. Here is an example:
http://forums.anandtech.com/showthread.php?t=1659798 ($210!)
These are interesting and educational because you can get an overview of the specific components that make up a bare-bones system, and a functional system.
Here are two other articles to help as well:
http://lifehacker.com/5151369/the-first+timers-guide-to-building-a-computer-from-scratch
http://lifehacker.com/5826509/how-to-build-a-computer-from-scratch-lesson-1-hardware-basics
Good luck and feel free to comment if you have any specific questions.