I suppose one way to solve the tendency for NPCs to get stuck (without having to do heavy path analysis) is to keep a record of the path followed by the player - then the NPCs do not have to think at all.
But if you have this problem with the NPCs, then i guess the zombies will get stuck too - but maybe that makes sense for mindless zombies 
Following the path of the player is a good idea. It could also lead to some interesting tactics - leaving a bread crumb trail for the zombies to follow.
I’ve implemented creature pathing that simply takes a step toward the current position of the target, and it actually works well enough in most cases (and also allows for tactics, such as getting them stuck behind things to escape).
Pathfinding isn’t the most trivial thing to implement, but can be fast, especially on a large-grained coordinate system, like Apocalypse Run. I wouldn’t worry about performance until you actually implement and test it. I followed this example to construct a speedy Java A* implementation.
Also see An Adventure Game, which has zombie pathing.