I have a mesh with tons of ngons, non-manfold stuff, poles, and a decent amount of tris. Should I just give up on the mesh, or can I somehow rescue it?
To deal with bad topology, but not having to start from scratch, It makes sense creating a new mesh and retopologizing. That is: using some form of vertex/edge/face snapping and/or a shrinkwrap modifier, you trace and receate your old mesh using proper topology. This technique is also useful when sculpting at a high poly count and then re-creating the mesh with less polygons.
It sounds daunting but in reality it is not a big deal at all.
Here are a few links that might help:
There is also a modifier called the remesh modifier, which does a sort of automatic retopology. I don't recommend it if you need clean, efficient topology, as it's often required to turn up the octree depth rather high, which can result in a dense mesh.
However, it's quite useful when you need a quick way to e.g. get a boolean operation to work or make volume rendering happy.
Sometimes it can help to just Remove Doubles.
In edit mode, choose edge select mode and type A once or twice to select all edges. Then just hit W and choose Remove Doubles.
In my case, I had simply deleted opposing faces and bridged the remaining edges. Removing doubles fixed the Bevel modifier not working.