Found an answer based on this post.
It seems that Matrix cannot be used as it can't create Trapezoid shapes which can occur in a 3d world.
So what is suggested there is to use the "Camera" class, as such:
Canvas canvas = new Canvas(bigBitmap);
Matrix matrix = new Matrix();
Camera camera = new Camera();
camera.save();
camera.translate(...,...,0);
camera.rotateX(...);
camera.rotateY(...);
camera.rotateZ(...);
camera.getMatrix(matrix);
int centerX = bigBitmap.getWidth() / 2;
int centerY = bigBitmap.getHeight() / 2;
matrix.preTranslate(-centerX, -centerY); //This is the key to getting the correct viewing perspective
matrix.postTranslate(centerX, centerY);
canvas.concat(matrix);
camera.restore();
canvas.drawBitmap(mSmallBitmap, matrix, new Paint());
Sadly, as you see, the coordinates aren't being used, so you need to either play with the numbers till you get it right, or find a formula to convert between the coordinates and the needed values.
I won't mark this answer as the correct one, because it doesn't fully fit the requirements of the original question (no coordinates are being used).
Plus I can't find how to deal with text while using this solution.
However, it does work, so it might be useful for others.
EDIT: It appears that the reason for setPolyToPoly to not scale the image at all, is that the first input array was incorrect: It was set as the size of the large bitmap, instead of the small one.
So, this is the correct code:
mLeftTop = new Point(370, 358);
mRightTop = new Point(650, 384);
mLeftBot = new Point(375, 972);
mRightBot = new Point(660, 942);
Canvas canvas = new Canvas(mBigBitmap);
final Matrix matrix = new Matrix();
matrix.setPolyToPoly(new float[]{0, 0,
mSmallBitmap.getWidth() - 1, 0,
0, mSmallBitmap.getHeight() - 1,
mSmallBitmap.getWidth() - 1, mSmallBitmap.getHeight() - 1},
0,
new float[]{mLeftTop.x, mLeftTop.y,
mRightTop.x, mRightTop.y,
mLeftBot.x, mLeftBot.y,
mRightBot.x, mRightBot.y
}
, 0, 4);
canvas.concat(matrix);
final Paint paint = new Paint();
paint.setAntiAlias(true);
canvas.drawBitmap(mSmallBitmap, 0, 0, paint);
However, for center-cropping, it still has this issue, but if you know the correct size of the rectangle before it got tilted, you can do the cropping before, and set it as the input.
As for the text, this is possible as usual, as the canvas stays with the matrix that was created.