Given two convex patches, how to find points/faces that have distance < x? The title says it all, given two convex patches, how to find points/faces that have distance &lt; x?  Can I use GJK for this case?

Convex patches are obtained from convex decomposition, see here. If I read it correctly, I don't think methods used in that paper can give points/faces that satisfy above condition.
Yes GJK is appropriate for this. 

The overall algorithm of GJK goes something like 

simplex = empty
direction n = arbitrary

while(not finished){

    find furthest point p1 in mesh 1 in direction n
    find furthest point p2 in mesh 2 in direction -n

    supplement simplex with point p1-p2

    if(simplex is tetrahedron) simplify simplex

    direction n = pick direction perpendicular to simplex pointing to origin

}


you can then use the simplex at the end of the loop to calculate the distance from it to the origin and set finished to true and you will get a collection of points on each mesh which make up a pair of faces that are closer than x.