Как сделать замену нечетных и четных символов в строке?

Ксли нельзя использовать StringBuilder, то можно попробовать массив. Например так

private string Replace(string inp, char c)
{
    var holder = new char[inp.Length];
    int counter = 1;
    for(int i=0; i<inp.Length; i++)
    {
        if (inp[i]!=c)
        {
            holder[i] = inp[i];
            continue;
        }
        if (counter%2==0)       
            holder[i] = '>';
        else        
            holder[i] = '<';
        counter++;
    }
    return new string(holder);
}

Проверка

Console.WriteLine(Replace("123!456!789!", '!'));

Вывод

123<456>789<

немного LINQ:

private void Do(string inputStringParam)
{
    var enumerable = inputStringParam.Select((c, i) =>
    {
        if (c != '!') return c;
        var isOdd = i / 2 == 1;
        return isOdd ? '<' : '>';
    });
    var newString = new string(enumerable.ToArray());
}

если нужно "считать" символы не по номеру строки, а по номеру вхождения '!':

private void Do(string inputStringParam)
{
    var i = 0;
    var enumerable = inputStringParam.Select(c =>
    {
        if (c != '!') return c;
        i++;
        var isOdd = i / 2 == 1;
        return isOdd ? '<' : '>';
    });
    var newString = new string(enumerable.ToArray());
}

или string.Concat(enumerable);? - не уверен что это лучше