XSLT output is verbose and messy

Question 1

I'm rather surprised that Xalan should be producing all those redundant namespace declarations. Here is Saxon's output for comparison:

<?xml version="1.0" encoding="UTF-8"?><newns:testRequest xmlns:newns="namespace/1.1">
     <newns:a>
        <b1 xmlns="namespace/1.1">
           <newns:c>cccc</newns:c>
           <newns:d>dddd</newns:d>
           <newns:e>eeee</newns:e>
        <newElement>NEW_VAL</newElement></b1>
        <newns:b2 attr="value">
           <newns:f>false</newns:f>
           <newns:g>2014-03-01</newns:g>
           <newns:h>true</newns:h>
        </newns:b2>
        <newns:b3>
        </newns:b3>
     </newns:a>
  </newns:testRequest>

If you want to make the dominant namespace newns be the default namespace, to reduce clutter further, you can change <xsl:copy> to <xsl:element name="{local-name()}" namespace="{namespace-uri()}">. This produces the output:

<?xml version="1.0" encoding="UTF-8"?>
<testRequest xmlns="namespace/1.1">
     <a>
        <b1>
           <c>cccc</c>
           <d>dddd</d>
           <e>eeee</e>
        <newElement>NEW_VAL</newElement></b1>
        <b2 attr="value">
           <f>false</f>
           <g>2014-03-01</g>
           <h>true</h>
        </b2>
        <b3>
        </b3>
     </a>
  </testRequest>

Here's the amended stylesheet:

<xsl:stylesheet
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:oldns="namespace/1.0"
    xmlns:newns="namespace/1.1"
    version="1.0">

    <xsl:param name="newnsParam">namespace/1.1</xsl:param>

    <!-- copy all document -->
    <xsl:template match="*">
        <xsl:element name="{local-name()}" namespace="{namespace-uri()}">
            <xsl:apply-templates select="*" />
        </xsl:element>
    </xsl:template>

    <xsl:template match="@*">
        <xsl:copy-of select="."/>
    </xsl:template>

    <!-- rename 'g' to 'newName' -->
    <xsl:template match="/oldns:testRequest/oldns:a/oldns:b1/oldns:g">
        <!-- if I don't set it with newns now, it will remain as oldns even after namespace change below -->
        <xsl:element name="newName" namespace="{$newnsParam}">
            <xsl:apply-templates select="@*|node()" />
        </xsl:element>
    </xsl:template>

    <!-- add 'newElement' -->
    <xsl:template match="/oldns:testRequest/oldns:a/oldns:b1">
        <!-- same as above, must set as newns now, and this one won't be qualified (why?) -->
        <xsl:element name="b1" namespace="{$newnsParam}">
            <xsl:apply-templates select="@*|node()" />
            <xsl:element name="newElement" namespace="{$newnsParam}">NEW_VAL</xsl:element>
        </xsl:element>
    </xsl:template>

    <!-- change namespace, but it makes every node redefine the namespace -->
    <xsl:template match="@oldns:*">
        <xsl:attribute name="newns:{local-name()}" namespace="{$newnsParam}">
            <xsl:value-of select="."/>
        </xsl:attribute>
    </xsl:template>

    <xsl:template match="oldns:*">
        <xsl:element name="{local-name()}" namespace="{$newnsParam}">
            <xsl:apply-templates select="node()|@*"/>
        </xsl:element>
    </xsl:template>

</xsl:stylesheet>

Question 2

I'm not sure if this works for you because I'm using a different xlst processor (xsltproc). Also my output with your original xslt does not completely look like your output.

So anyway:
I have mainly removed the namespace attribute from xlst and add two times the namespace prefix "newns".

Try this:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:oldns="namespace/1.0"
    xmlns:newns="namespace/1.1"
    version="1.0">

    <xsl:param name="newnsParam">namespace/1.1</xsl:param>

    <!-- copy all document -->
    <xsl:template match="@*|node()">
        <xsl:copy>
            <xsl:apply-templates select="@*|node()" />
        </xsl:copy>
    </xsl:template>

    <!-- rename 'g' to 'newName' -->
    <xsl:template match="/oldns:testRequest/oldns:a/oldns:b1/oldns:g">
        <!-- if I don't set it with newns now, it will remain as oldns even after namespace change below -->
        <xsl:element name="newns:newName">
            <xsl:apply-templates select="@*|node()" />
        </xsl:element>
    </xsl:template>

    <!-- add 'newElement' -->
    <xsl:template match="/oldns:testRequest/oldns:a/oldns:b1">
        <!-- same as above, must set as newns now, and this one won't be qualified (why?) -->
        <xsl:element name="newns:b1" >
            <xsl:apply-templates select="@*|node()" />
            <xsl:element name="newns:newElement">NEW_VAL</xsl:element>
        </xsl:element>
    </xsl:template>

    <!-- change namespace, but it makes every node redefine the namespace -->
    <xsl:template match="@oldns:*">
        <xsl:attribute name="newns:{local-name()}">
            <xsl:value-of select="."/>
        </xsl:attribute>
    </xsl:template>
    <xsl:template match="oldns:*">
        <xsl:element name="newns:{local-name()}">
            <xsl:apply-templates select="node()|@*"/>
        </xsl:element>
    </xsl:template>

</xsl:stylesheet>

Which generates the following output (at least with xsltproc):

<?xml version="1.0"?>
<newns:testRequest xmlns:newns="namespace/1.1">
     <newns:a>
        <newns:b1>
           <newns:c>cccc</newns:c>
           <newns:d>dddd</newns:d>
           <newns:e>eeee</newns:e>
        <newns:newElement>NEW_VAL</newns:newElement></newns:b1>
        <newns:b2 attr="value">
           <newns:f>false</newns:f>
           <newns:g>2014-03-01</newns:g>
           <newns:h>true</newns:h>
        </newns:b2>
        <newns:b3>
        </newns:b3>
     </newns:a>
  </newns:testRequest>