Color state is changing when I am deleting item from list and do setState((){})

In your case, the setState will rebuild every time. If you want to work with keys, a new wrapper of ListTile must be created.

But, there is another alternative. In the initState, a list of random colors can be created:

class MyList extends StatefulWidget {
  const MyList({ Key key }) : super(key: key);

  @override
  _MyListState createState() => _MyListState();
}

class _MyListState extends State<MyList> {
  final List<int> _allExpenses = [2, 4, 5, 6, 9, 10, 22];
  
  List<Color> _colors;
  
  @override
  void initState(){
    super.initState();
    _colors = [
      for(final _ in _allExpenses)
        Color(Random().nextInt(0xffffffff)),
    ];
  }
  
  void removeOne(int index){
    setState(() {
       _allExpenses.removeAt(index);
      _colors.removeAt(index);
    });
  }
  
  
  @override
  Widget build(BuildContext context) {
    return ListView(
      children: [
        for(int i = 0; i < _allExpenses.length; i++)
          ListTile(
            //key: ObjectKey(expense),
            onTap: () => removeOne(i),
            leading: CircleAvatar(
              radius: 20,
              backgroundColor: _colors[i],
              child: Icon(Icons.account_circle),
            ),
            title: Text("Test ${_allExpenses[i]}"),
          ),
      ]
    );
  }
}

That is a good alternative because you can control the needed memory for those random colors. That logic can be extended to ChangeNotifiers with their notifyListeners() using the addListener() in the initState:

@override initState(){
  ...
  myChangeNotifierList.addListener(() => setState((){}));
}

There is another alternative where you delegate the responsibility of handling the random color and keeping the state of each list tile.

class MyListWithKeys extends StatefulWidget {
  const MyListWithKeys({ Key key }):  super(key: key);


  @override
  _MyListWithKeysState createState() => _MyListWithKeysState();
}

class _MyListWithKeysState extends State<MyListWithKeys> {
  final List<int> _allExpenses = [2, 4, 5, 6, 9, 10, 22];
  
  void removeOne(int expense){
    setState(() {
       _allExpenses.remove(expense);
    });
  }
  
  @override
  Widget build(BuildContext context) {
    return ListView(
      children: [
        for(final expense in _allExpenses)
          MyTile(
            key: ObjectKey(expense),
            expense: expense,
            onTap: () => removeOne(expense),
          ),
      ]
    );
  }
}

class MyTile extends StatefulWidget {
  const MyTile({
    Key key,
    @required this.expense,
    @required this.onTap,
  }) : assert(expense != null),
       assert(onTap != null),
       super(key: key);
  
  final int expense;
  final VoidCallback onTap;

  @override
  _MyTileState createState() => _MyTileState();
}

class _MyTileState extends State<MyTile> {
  Color _color;
  
  @override
  void initState() {
    super.initState();
    _color = Color(Random().nextInt(0xffffffff));
  }
  
  @override
  Widget build(BuildContext context) {
    return ListTile(
      onTap: widget.onTap,
      leading: CircleAvatar(
        radius: 20,
        backgroundColor: _color,
        child: Icon(Icons.account_circle),
      ),
      title: Text('Test ${widget.expense}'),
    );
  }
}