You could do something like 
while (s/((^|\>)[^\<]*?)\>/$1\&gt\;/g) { 1; }

[download]
Explained:
Look for the begin of the string or any closing > in place. From here, grab everything which is no opening < until you find the next closing >. Return the grabbed thing but replace the unmatched > by &gt;.
Do this in a while loop, because the first run may not catch all unmatched >'s until no new places are found.

The only 100% working solution would be using an XML/HTML parser. The sample above will mix up HTML-code like <a name=">here">

edit: Sorry, I just saw that my solution is working on the wrong side.

edit2: Here is the correct solution:

while (s/\<([^\>]*?(\<|$))/\&lt\;$1/g) { 1; }

[download]
Explained:
Every < which has no > (^\&gt; - match everything but >, *? = match 0 to as few as possible chars) until the earliest next < or and end-of-string is replaced.
Has been tested using the string 
<<html><x<y</html><

[download]

Notice:
  • The same thing (using a XML/HTML parser for best results) is also true for this one.
  • Remember using /s if you're processing a multiline string

    • In reply to Re: substitution on by Sewi
    in thread substitution on by Anonymous Monk

    Title:
    Use:  <p> text here (a paragraph) </p>
    and:  <code> code here </code>
    to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.