Here is a fully functional example using SAX parser. It is adapted to your case with minimal changes from this example
The actual replacement takes place in MyCopyHandler#endElement() and MyCopyHandler#startElement() and the XML element text content is collected in MyCopyHandler#characters(). Note the buffer maintenance too - it is important in handling mixed element content (text and child elements)
I know XSLT solution is also possible, but it is not that portable. 
public class XMLReplace {
    /**
     * @param args
     * @throws SAXException
     * @throws ParserConfigurationException
     */
    public static void main(String[] args) throws Exception {
        final String str = "<root> Hello <nested attr='Hello'> Text </nested>  Hello world Hello Programming </root>";
        SAXParserFactory spf = SAXParserFactory.newInstance();
        SAXParser parser = spf.newSAXParser();
        XMLReader reader = parser.getXMLReader();
        reader.setErrorHandler(new MyErrorHandler());
        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        PrintWriter out = new PrintWriter(baos);
        MyCopyHandler duper = new MyCopyHandler(out);
        reader.setContentHandler(duper);
        InputSource is = new InputSource(new StringReader(str));
        reader.parse(is);
        out.close();
        System.out.println(baos);
    }
}
class MyCopyHandler implements ContentHandler {
    private boolean namespaceBegin = false;
    private String currentNamespace;
    private String currentNamespaceUri;
    private Locator locator;
    private final PrintWriter out;
    private final StringBuilder buffer = new StringBuilder();
    public MyCopyHandler(PrintWriter out) {
        this.out = out;
    }
    public void setDocumentLocator(Locator locator) {
        this.locator = locator;
    }
    public void startDocument() {
    }
    public void endDocument() {
    }
    public void startPrefixMapping(String prefix, String uri) {
        namespaceBegin = true;
        currentNamespace = prefix;
        currentNamespaceUri = uri;
    }
    public void endPrefixMapping(String prefix) {
    }
    public void startElement(String namespaceURI, String localName, String qName, Attributes atts) {
        // Flush buffer - needed in case of mixed content (text + elements)
        out.print(buffer.toString().replaceAll("Hello", "HI"));
        // Prepare to collect element text content
        this.buffer.setLength(0);
        out.print("<" + qName);
        if (namespaceBegin) {
            out.print(" xmlns:" + currentNamespace + "=\"" + currentNamespaceUri + "\"");
            namespaceBegin = false;
        }
        for (int i = 0; i < atts.getLength(); i++) {
            out.print(" " + atts.getQName(i) + "=\"" + atts.getValue(i) + "\"");
        }
        out.print(">");
    }
    public void endElement(String namespaceURI, String localName, String qName) {
        // Process text content
        out.print(buffer.toString().replaceAll("Hello", "HI"));
        out.print("</" + qName + ">");
        // Reset buffer
        buffer.setLength(0);
    }
    public void characters(char[] ch, int start, int length) {
        // Store chunk of text - parser is allowed to provide text content in chunks for performance reasons
        buffer.append(Arrays.copyOfRange(ch, start, start + length));
    }
    public void ignorableWhitespace(char[] ch, int start, int length) {
        for (int i = start; i < start + length; i++)
            out.print(ch[i]);
    }
    public void processingInstruction(String target, String data) {
        out.print("<?" + target + " " + data + "?>");
    }
    public void skippedEntity(String name) {
        out.print("&" + name + ";");
    }
}
class MyErrorHandler implements ErrorHandler {
    public void warning(SAXParseException e) throws SAXException {
        show("Warning", e);
        throw (e);
    }
    public void error(SAXParseException e) throws SAXException {
        show("Error", e);
        throw (e);
    }
    public void fatalError(SAXParseException e) throws SAXException {
        show("Fatal Error", e);
        throw (e);
    }
    private void show(String type, SAXParseException e) {
        System.out.println(type + ": " + e.getMessage());
        System.out.println("Line " + e.getLineNumber() + " Column " + e.getColumnNumber());
        System.out.println("System ID: " + e.getSystemId());
    }
}