The following is working for me, IMHO better, than using a ellipsize based solution.
void adjustTextScale(TextView t, float max, float providedWidth, float providedHeight) {
    // sometimes width and height are undefined (0 here), so if something was provided, take it ;-)
    if (providedWidth == 0f)
        providedWidth = ((float) (t.getWidth()-t.getPaddingLeft()-t.getPaddingRight()));
    if (providedHeight == 0f)
        providedHeight = ((float) (t.getHeight()-t.getPaddingTop()-t.getPaddingLeft()));
    float pix = TypedValue.applyDimension(TypedValue.COMPLEX_UNIT_DIP, 1, getResources().getDisplayMetrics());
    String[] lines = t.getText().toString().split("\\r?\\n");
    // ask paint for the bounding rect if it were to draw the text at current size
    Paint p = new Paint();
    p.setTextScaleX(1.0f);
    p.setTextSize(t.getTextSize());
    Rect bounds = new Rect();
    float usedWidth = 0f;
    // determine how much to scale the width to fit the view
    for (int i =0;i<lines.length;i++){
        p.getTextBounds(lines[i], 0, lines[i].length(), bounds);
        usedWidth = Math.max(usedWidth,(bounds.right - bounds.left)*pix);
    }
    // same for height, sometimes the calculated height is to less, so use §µ{ instead
    p.getTextBounds("§µ{", 0, 3, bounds);
    float usedHeight = (bounds.bottom - bounds.top)*pix*lines.length;
    float scaleX = providedWidth / usedWidth;
    float scaleY = providedHeight / usedHeight;
    t.setTextSize(TypedValue.COMPLEX_UNIT_PX,t.getTextSize()*Math.min(max,Math.min(scaleX,scaleY)));
}