As Ulrike said, the geometry package works fine. You customize the stock size as required in the geometry package definition, and then proceed and define a new label with necessary dimensions. Here's a quick and dirty example:
\documentclass{article}
\usepackage[paperwidth=10in, paperheight=7in]{geometry} % Define paper stock size here
\usepackage[newdimens]{labels}
\numberoflabels=20
% These are the label parameters. Customize to your heart's content.
\LabelCols=5 % Number of columns of labels per page
\LabelRows=4 % Number of rows of labels per page
\LeftPageMargin=7mm % These four parameters give the
\RightPageMargin=7mm % page gutter sizes. The outer edges of
\TopPageMargin=15mm % the outer labels are the specified
\BottomPageMargin=15mm % distances from the edge of the paper.
\InterLabelColumn=2mm % Gap between columns of labels
\InterLabelRow=0mm % Gap between rows of labels
\LeftLabelBorder=5mm % These four parameters give the extra
\RightLabelBorder=5mm % space used around the text on each
\TopLabelBorder=5mm % actual label.
\BottomLabelBorder=5mm
\begin{document}
% Here's your label definition
\begin{labels}
Me
My address
My City, State, Zipcode
My Brother
His address
His City, State, Zipcode
\end{labels}
\end{document}
Admittedly, you'll need to do some calculations and assumptions to find all the parameters (assuming your label size is fixed), but here are the handy formulas (from the labels package):
LabelRows × Label height + (LabelRows − 1) × InterLabelRow = paperheight − TopPageMargin − BottomPageMargin
LabelColumns × Label width + (LabelColumns − 1) × InterLabelColumn =
paperwidth − LeftPageMargin − RightPageMargin