Replace parameter in lambda expression

I would do it this way:

Write a parameter-replacer expression-visitor that manipulates the original expression as follows:

1. Gets rid of the parameter you don’t want entirely from the lambda signature.
2. Replaces all uses of the parameter with the desired indexer expression.

Here’s a quick and dirty sample I whipped up based on my earlier answer on a different question:

public static class ParameterReplacer
{
    // Produces an expression identical to 'expression'
    // except with 'source' parameter replaced with 'target' expression.     
    public static Expression<TOutput> Replace<TInput, TOutput>
                    (Expression<TInput> expression,
                    ParameterExpression source,
                    Expression target)
    {
        return new ParameterReplacerVisitor<TOutput>(source, target)
                    .VisitAndConvert(expression);
    }

    private class ParameterReplacerVisitor<TOutput> : ExpressionVisitor
    {
        private ParameterExpression _source;
        private Expression _target;

        public ParameterReplacerVisitor
                (ParameterExpression source, Expression target)
        {
            _source = source;
            _target = target;
        }

        internal Expression<TOutput> VisitAndConvert<T>(Expression<T> root)
        {
            return (Expression<TOutput>)VisitLambda(root);
        }

        protected override Expression VisitLambda<T>(Expression<T> node)
        {
            // Leave all parameters alone except the one we want to replace.
            var parameters = node.Parameters
                                 .Where(p => p != _source);

            return Expression.Lambda<TOutput>(Visit(node.Body), parameters);
        }

        protected override Expression VisitParameter(ParameterExpression node)
        {
            // Replace the source with the target, visit other params as usual.
            return node == _source ? _target : base.VisitParameter(node);
        }
    }
}

Usage for your scenario (tested):

var zeroIndexIndexer = Expression.MakeIndex
        (Expression.Constant(foos),
         typeof(List<Foo>).GetProperty("Item"), 
         new[] { Expression.Constant(0) });


// .ToString() of the below looks like the following: 
//  () =>    (value(System.Collections.Generic.List`1[App.Foo]).Item[0].a
//         *  value(System.Collections.Generic.List`1[App.Foo]).Item[0].b)
var exp1Clone = ParameterReplacer.Replace<Func<Foo, int>, Func<int>>
                  (exp0, exp0.Parameters.Single(), zeroIndexIndexer);