OUTER: while (...) {
    while (...) {
        ...
        last OUTER;
    }
}
[download]

/me stands back and waits for the slapped forehead sound.

You need labelled loops.

OUTER: while ($something_is_true) {
  INNER: while ($some_other_thing_is_true) {
    last OUTER if $you_want_to_quit_outer_loop;
    last INNER if $you_want_to_quit_inner_loop;
  }
}
[download]

See Compound statements in perldoc perlsyn for details.

Update: Added ':' to labels.

GrandFather and davorg have your answer above. I just wanted to add that it often reads better to label your loops with what they're iterating over, rather than their structure.

For example, say you're processing files and records line-by-line. You could do this:

OUTER:
while ( $more )
{
    INNER:
    while ( $still_more )
    {
        # ...
        last OUTER if $done_with_files;
        last INNER if $done_with_lines;
    }
}
[download]

FILE:
while ( $more )
{
    LINE:
    while ( $still_more )
    {
        # ...
        last FILE if $done_with_files;
        last LINE if $done_with_lines;
    }
}
[download]