From nearlyfreespeech's website, they state that the following don't work well:
Are there any Python web frameworks that work well on NearlyFreeSpeech?
WSGI can run on top of CGI, and popular frameworks typically run on top of WSGI, but performance is quite another issue -- since a CGI service starts afresh on each hit, any framework you may be using will need to reload from scratch each and every time, and that (in addition to opening a new connection to a DB, etc, which is basically inevitable with CGI) will make things pretty sluggish on anything but the tiniest, lightest frameworks.
Maybe something like WebOb might be tolerable, but you'll need to do some tests to check even that (how loaded those servers are is, of course, a big part of the puzzle, and you just can't tell except by testing).