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.