How to extend immutable types in Java

As you said. The team can appear in different circumstances. These circumstances are the context giving the team the additional attributes.

Therefore I suggest using composition for each different context that add's data.

public class TeamWithColor {
    public final Team team;
    public final TeamColor teamColor;

    public Team(Team team, TeamColor teamColor) {
        this.team = team;
        this.teamColor = teamColor;
    }
}

Maybe you'll have :

public class TeamDuringOlimpics{
    public final Team team;
    public final TeamColor teamColor;
    public final TeamFlag teamFlag;

    public Team(Team team, TeamColor teamColor, TeamFlag teamFlagTeamFlag teamFlag) {
        this.team = team;
        this.teamColor = teamColor;
        this.teamFlag = teamFlag;
    }    
}

Composition sounds like a good option for adding contextual data that is required to be mutable.

In Java immutable classes are usually marked final and cannot be extended. See String as an example. That rules out option number 2.

Be weary of using Pairs. There are many good reasons the Pair type has not been added to Java. In this case your data is better modeled by creating a new data type (i.e. thru composition).

Recommended best practices for creating immutable classes: http://www.javapractices.com/topic/TopicAction.do?Id=29