This is one of best examples for PDF::API2 I ever found. ++ However, it has few problems, so corrected version is below:

#!/usr/bin/perl -w

use strict;

use PDF::API2;
my $newpdf = new PDF::API2;

my $newfilename = my $filename = shift @ARGV || die "usage: $0 file.pd
+f";
$newfilename =~ s/(\.pdf)/-resized$1/i;

my $oldpdf = PDF::API2->open($filename);

for my $pg ( 1 .. $oldpdf->pages ) {
    my $img = $newpdf->pdfimageobj( $oldpdf, $pg );

    my $page = $newpdf->page();
    $page->mediabox( 6 * 72, 9 * 72 );    # There's 72 postscript poin
+ts in +an inch

      my $gfx = $page->gfx;
      $gfx->pdfimage(
        $img,
        0.5 * 72,    # half inch from the left
        0.5 * 72,    # half inch from the bottom
        5 / 8.5,     # x scale = new width / old width
        8 / 11       # y scale = new height / old height
    );
}

$newpdf->saveas($newfilename);
$oldpdf->end();
[download]

I can also confirm that it embeds fonts (and only subset of used ones).
Update: fixed code