Да, кортежи неизменны. Анонимные типы также являются неизменяемыми. Вы должны использовать свой собственный универсальный тип:
public class Pair<T, U>
{
public Pair() {
}
public Pair(T first, U second) {
this.First = first;
this.Second = second;
}
public T First { get; set; }
public U Second { get; set; }
};