Take a look at Data::Rmap. You'll be relying upon the uniqueness of your placeholders, but this seems to produce the output your require:

use warnings;
use strict;
use HTML::TreeBuilder;
use Clone qw(clone);
use Data::Rmap qw[rmap_scalar];

my $newHTML =
  ['div', {class => 'ourobject'},
    ['script', {language => 'JavaScript', type => 'text/JavaScript'},
      'embedLabTutorClient("VIEW", "URL", WWW, HHH)',
    ],
    ['noscript',
      ['object',
        {classid=>"CLSID:ReleaseCLSID", width=>'WWW', height=>'HHH', v
+iewastext=>'1'},
        ['param', {name=>'ViewSettingsUrl', value=>'URL'}],
        ['param', {name=>'ViewName', value=>'VIEW'}],
      ]
    ]
  ];


my $objUrl = 'somewhere/object.obj';
my $objView = 'erewhon';
my $objWidth = 255;
my $objHeight = 127;

my $copy = clone ($newHTML);

# Perform 'global' ssubstitutions on $copy here
rmap_scalar{ s/WWW/$objWidth/  } $copy;
rmap_scalar{ s/HHH/$objHeight/ } $copy;
rmap_scalar{ s/VIEW/$objView/  } $copy;
rmap_scalar{ s/URL/$objUrl/    } $copy;

my $element = HTML::Element->new ('root');

$element->push_content ($copy);
print $element->as_HTML(undef, '   ', {});

__END__
c:\test>junk
<root><div class="ourobject">
      <script language="JavaScript" type="text/JavaScript">embedLabTut
+orClient("erewhon", "somewhere/object.obj", 255, 127)</script>
      <noscript>
         <object classid="CLSID:ReleaseCLSID" height=127 viewastext=1 
+width=255>
            <param name="ViewSettingsUrl" value="somewhere/object.obj"
+>
            <param name="ViewName" value="erewhon">
         </object>
      </noscript>
   </div></root>
[download]