This is really two questions, but they are so similar, and to keep it simple, I figured I'd just roll them together:

Firstly: Given an established python project, what are some decent ways to speed it up beyond just plain in-code optimization?
Secondly:  When writing a program from scratch in python, what are some good ways to greatly improve performance?

For the first question, imagine you are handed a decently written project and you need to improve performance, but you can't seem to get much of a gain through refactoring/optimization.  What would you do to speed it up in this case short of rewriting it in something like C?
This is the procedure that I try to follow:

 import psyco; psyco.full()
  If it's not fast enough, run the code through a profiler, see where the bottlenecks are. (DISABLE psyco for this step!)
  Try to do things such as other people have mentioned to get the code at those bottlenecks as fast as possible.
 Stuff like [str(x) for x in l] or [x.strip() for x in l] is much, much slower than map(str, x) or map(str.strip, x). 
 After this, if I still need more speed, it's actually really easy to get PyRex up and running. I first copy a section of python code, put it directly in the pyrex code, and see what happens. Then I twiddle with it until it gets faster and faster.
Speeding Up Python