So far, everyone has some really great advice for ya! What I'd probably try first is to make sure there are no air pockets. If you hear any gurgling noise when you turn your heater on in the car, you've got a good sized air pocket in the system. Get that front end up in the air as high as possible, and with a cold engine, take the cap off the radiator and let the car come up to temperature. That'll get rid of the air in the system.
I'd also get a thermostat back in there, a colder one is okay, as long as it isn't below 175°. If you don't want to run a thermo at all, at least cut the basket off an old one and put the "washer" back in. This will give the system necessary backpressure. Think of it like running water from a hose. If you put your finger over the opening, the water pressurizes and you get less water moving, but what is moving has more velocity. This will allow the water in the block to sit there a little longer and allow necessary heat transfer between engine and water before returning to the radiator...
As for the clutch fan, I know the one on my truck worked, because going up hills in summer, it would spin up and I'd lose most of my power, then after about a minute or two, I'd hear it release, the power would return, and the temp would be down a bit. Go to Toyota and buy a tube of the goop that's installed inside the fan's clutch. clean the old stuff out and replace it with the new stuff and it'll be just like new.
If that doesn't get it back to normal, you may be running really lean, cam adjustments could possibly cause that, but I think o2 sensor would be more of a cause.