Here is a slightly different take on the suggestion by Eirikur that achieves the same but without querying the system views. I've also opted to use dynamic sql to generate the additional xml section rather than a search/replace. This ensures that non-xml safe characters in the node value are escaped properly but you need to assess the risk of using dynamic SQL and if you trust what is going to be invoking the logic.
DECLARE @XML XML = '<Attribute>
<A1>1111</A1>
<A2>2222</A2>
<A4>4444</A4>
</Attribute>';
DECLARE @n VARCHAR(100) = 'A3';
DECLARE @v-2 VARCHAR(100) = 'New value';
DECLARE @XmlToInsert XML
DECLARE @SQL NVARCHAR(200)
SET @SQL = N'SELECT @XmlToInsert = (SELECT @v-2 FOR XML PATH(''' + @n + '''))'
EXEC sys.sp_executesql @SQL, N'@XmlToInsert XML OUTPUT, @v-2 VARCHAR(100)'
, @XmlToInsert = @XmlToInsert OUTPUT
IF @XML.value('count(/Attribute/node())', 'int') > 0
SET @XML.modify('insert sql:variable("@XmlToInsert") before (/Attribute/node()[local-name(.) > sql:variable("@n") ])[1]')
ELSE
SET @XML.modify('insert sql:variable("@XmlToInsert") as first into (/Attribute)[1]')
SELECT @XML