What a database like PostGIS does to speed this up is to first do an index, bounding box compare. It first finds all polygons that have bounding boxes interersecting with the bounding box of the line. The problem in your case might be that the linestring is long and will have a very big bounding box intersecting many polygons that is of no interest.
If the lines are very long you will probably also have to work with geodetic functions that is much more complex and slow than planar functions.
It might be quite complex to make things run smooth.
Why do you not want to rely on a database? That will not solve all your problems, but there is a lot of built in optimisations in PostGIS for instance. There you also have the geodetic calculations of intersection if you need it.
Update: I read your question again and realised that you are not using the linestring the trac forms but each vertex.
I think you are on the wrong trac ;)
Both because you are missing to check if the edge between the vertexpoints intersects the polygon and because you are moving the iteration between the vertex points to python instead of some C implementation which I think is much faster. Then you have that problem with indexes. To make things faster you will have to build and handle some sort of spatial index.
At the other hand, if you are doing this much of the work in your own code, why don't you do the intersection test too. That test is just a point in polygon test if you are dealing with the vertex points. Google for "point in polygon" and you will find several algorithms.
But, I would go for a database driven approach. That will give you the possibilities to use spatial indexes.
/Nicklas