while my attempts at a look-ahead/look-behind combination failed on the entire string, i was able to accomplish it by split'ing it off first...

# $str =~  s/(?<!bar)(.*?)foo(?!.*?qux)/$1.'123'/eg;   # one of severa
+l failed attempts

$str =
  join '',                               # glue back together
    map { s/(?<!bar)(.*?)foo(?!.*?qux)/$1 .'123'/eg; $_ }  # replace o
+n the non- bar-foo-qux elements.
    split /(bar.*?foo.*?qux)/, $str;     # get elements that are eithe
+r the bar-foo-qux form or not.
[download]

Update: BrowserUK's approach is very much nicer than this one..