I recommend using Erin Catto's approach that he introduced at the GDC this year:
It is conceptually a hybrid of Brian Mirtich's conservative advancement method and bisection. I ported it to 3D and it works great in practice. The edge distance function in 3D is non-trivial though (it is non convex function), but I am sure you can figure it out.
You can find a 2D reference implementation in the Box2D source. You can find good discussions of conservative advancement here:
In my *personal* experience the original conservative advancement is too slow for real-time simulation. Worst cases like a rigid body rotating over the edge of another one are a common situation in games and take hundreds of iterations. E.g. a book falling of a table.