I have a few observations which are too long for comments. Here's a summary.
Any algorithm to solve your problem exactly can be used to solve linear programs exactly (i.e., "strong linear programming", which is used in Sariel's solution, and presently does not have a polynomial time algorithm).
The natural follow-up is if approximate solutions (i.e., "weak linear programming") can provide a solution. While the answer is yes, it appears that the stopping condition for this procedure requires quantities which, to the best of my knowledge, can not be computed in polynomial time. (i.e., the algorithm finds something good, but certifying this is difficult.) My main suggestion here is to make a meaningful definition of an "$\epsilon$-optimal solution" for your problem, in which case this approach is tractable. (This strategy effectively throws out tiny faces of the polyhedron.)
In general, while thinking about your present statement of your problem, I kept running into efficiency considerations. But there's reasonable intuition to this: the objects we're throwing around -- vertices, faces, etc. -- are discrete, and exponentially abundant.
(1.) Suppose we have an algorithm which exactly solves your problem. Notice that any exposed point of any face containing the provided midpoint will be an exact solution to the original linear program. So proceed as follows. Add a new linear constraint saying that the original objective value must be equal to the optimal one (which we now know), and set a new objective saying to maximize the first coordinate of the solution. Repeat this procedure one time for each dimension, each time adding a constraint and choosing a new coordinate to maximize. This process will reduce the dimension of the solution each time; necessarily, when the process completes, we have a 0-dimensional affine set, meaning a single point. Thus with $\mathcal O(d)$ iterations of your midpoint-solving algorithm (and only increasing the problem description by an amount polynomial in $d$ each time), strong linear programming is solved. This shows that while Sariel's solution requires strong linear programming, an exact solution to your question can not avoid it. (Edit: note that my proof supposes a compact polyhedron (a polytope) as input; otherwise it has to work a little harder to find vertices.)
(2.) Here's an iterative scheme, using a full blown convex solver in each iteration, whose solutions will converge to a mild notion of midpoint solution. Choose a positive yet decreasing sequence of penalty parameters $\{\lambda_i\}_{i=1}^\infty\downarrow 0$; it is reasonable to have these go down geometrically, i.e. $\lambda_i = 2^{-i}$. Now, for each $i$, approximately minimize the convex function
$$\langle c,x\rangle - \lambda_i\sum_{j=1}^m \ln(\langle a_j,x\rangle - b),$$
where $\langle c,x\rangle$ is your original objective, and $j$ ranges over the $m$ original constraints, now placed in the objective via logarithmic barriers (note, this is standard). Now if we think about the minimizing face (of largest dimension) of your polyhedron, notice that for
sufficiently small $\lambda_i$ and tolerance $\tau$ to your convex opt black box, your approximate optimum will be close to this face, however the barriers will push it as far as possible from the other constraints. Said another way, as $\lambda_i$ decreases, the original linear objective will eventually dominate some finicky barriers that were keeping you from the appropriate face, but won't impact the barriers keeping you from other boundaries, in particular those of the target face.
In a perfect world, we would sit down and analytically determine a perfect value $\lambda$, or at least a stopping time so you don't have to solve, well, infinitely many problems. Unfortunately, this seems tough. One idea is, say, to determine the smallest width of any face having dimension greater than 0; this is a well defined minimization problem with positive optimum, because there are finitely many faces (and width is computed relative to each). With this, we can set $\lambda$ small enough that the influence of the barriers is tiny within the center of every face. Unfortunately, there could be exponentially many faces, so computing this quantity is nonsense.
All the stopping conditions I could come up with had these sorts computational difficulties. (Moreover, many could again be used to turn this into a strong linear programming solver.)
For this reason, my recommendation is to construct a notion of ``$\epsilon$-close optimal midpoint'', and solve for it by choosing $\lambda$ and your convex opt black box tolerance $\tau$ appropriately. I think this is a reasonable choice because you may really not care about faces that have largest width at most $\epsilon$.
(Some final comments.) It seems the notion of "midpoint" is crucial; Sasho's comment points out that the centroid (center of mass?) is an extremely difficult problem, whereas finding, say, the largest inscribed ball is easy. The logarithmic barriers I have suggested above will in general not be consistent with either of these midpoint notions. On the other hand, for the barriers and the ball, you can derive a lower bound on the distance from your centroid to the relative boundary of the face; maybe this is more useful to you?
Lastly, from your description, I believe you meant the "target face" to have as high a dimension as possible? This is well defined, however there are also solution faces for all possible smaller dimensions as well. Anyway, both Sariel's approach and the barrier approach above will work with the face of largest dimension.