This question is done and dusted but it is such a good one (together with the existing answers) for demonstrating and encapsulating the different ways Associations can be modified, that I'd like to belatedly summarise while suggesting some other "takeaways". In particular, how it can further highlight a "mutable" and "immutable" dichotomy or perhaps more accurately, a potential synergy.

The OP's attempt:

The initial OP attempt for a single association

x = <|"firstValue" -> True, "isFirstValueTrue" -> False|>;
SetAttributes[f, HoldAll];
f[x_] := If[x[["firstValue"]], x[["isFirstValueTrue"]] = True, x[["isFirstValueTrue"]] = False];
f@x;
x

(* <|"firstValue" -> True, "isFirstValueTrue" -> True|>*)

works as intended because modifying a component is performed using a named variable within Part in a similar vein to the way in which such modifications are performed in Lists

ls = {1, 2, 3};
ls[[2]] = 0.5; 
ls
(* {1, 0.5, 3} *)

In lists however, Set cannot use Part without a named variable:

{1, 2, 3}[[2]] = 0.5

Set::setps: {1,2,3} in the part assignment is not a symbol. >>

The same principle applies to Associations as was observed by the OP when applying f to xx's individual associations (note xx is used here to denote multiple associations instead of the original x)

xx = {
   <|"firstValue" -> True, "isFirstValueTrue" -> False|>,
   <|"firstValue" -> True, "isFirstValueTrue" -> True|>,
   <|"firstValue" -> False, "isFirstValueTrue" -> False|>,
   <|"firstValue" -> False, "isFirstValueTrue" -> True|>
   };

f /@ xx

Set::setps: <|firstValue->True,isFirstValueTrue->False|> in the part assignment is not a symbol. >>

This suggests a way of rescuing this idiomatic attempt by explicitly naming xx's elements. Suppose for example, the following are/were defined:

x1 = <|"firstValue" -> True, "isFirstValueTrue" -> False|>;
x2 = <|"firstValue" -> True, "isFirstValueTrue" -> True|>;
x3 = <|"firstValue" -> False, "isFirstValueTrue" -> False|>;
x4 = <|"firstValue" -> False, "isFirstValueTrue" -> True|>;

xx = Hold@{x1, x2, x3, x4};

in which case f can now be applied to the constituent Associations since they can now be symbolically referenced:

Map[f, xx, {2}] // ReleaseHold

(* {True, True, False, False} *)

and after releasing we get the required transformation of xx.

xx // ReleaseHold

 (*
 {
<|"firstValue" -> True, "isFirstValueTrue" -> True|>,
<|"firstValue" -> True, "isFirstValueTrue" -> True|>,
<|"firstValue" -> False, "isFirstValueTrue" -> False|>,
<|"firstValue" -> False, "isFirstValueTrue" -> False|>
}
*)

Note that in this mutable approach, AssociateTo could have been used to perhaps add readability

f[x_] := AssociateTo[x, "isFirstValueTrue" -> x@"firstValue"]

but at any rate, this "solution" is clearly unwieldy not only from the point of view of having to alternate between Hold and ReleaseHold but also from introducing subsidiary, symbolic definitions, x1, ..., x4. This was alluded to in Leonid Shifron's answer to another question describing the advantages of immutability since in certain contexts ...

... should you use symbols / their DownValues, you'd have to generate new symbols and then manage them - monitor when they are no longer needed and release them. This is a pain in the neck ...

Hence in this case, removing xx doesn't automatically remove x1, ..., x4 (here OwnValues but the same principle applies) while conversely, removing any of x1, ..., x4 changes xx, something not necessarily expected or desired.

The great thing about the introduction of Associations however, is that by infusing immutability no such artifice is needed or future surprises likely as all the bookkeeping is handled automatically behind the scenes.

Several solutions were provided in the other responses each of which is now recast with Query equivalents together with MyReplacePart, MyReplacePartFix that forms the basis of these answers' immutable/mutable approaches. All of the following solutions use the xx definition which is restored as needed (in the mutable approaches):

SetAttributes[Restore, HoldAll];
Restore[xx_] := xx = {
    <|"firstValue" -> True, "isFirstValueTrue" -> False|>,
    <|"firstValue" -> True, "isFirstValueTrue" -> True|>,
    <|"firstValue" -> False, "isFirstValueTrue" -> False|>,
    <|"firstValue" -> False, "isFirstValueTrue" -> True|>
    };
Restore@xx;

and all solutions generate the following output (or a visual equivalent as in solution 7):

(*
 {
<|"firstValue" -> True, "isFirstValueTrue" -> True|>,
<|"firstValue" -> True, "isFirstValueTrue" -> True|>,
<|"firstValue" -> False, "isFirstValueTrue" -> False|>,
<|"firstValue" -> False, "isFirstValueTrue" -> False|>
}
*)

Collection of Immutable/Mutable Solutions

1. MapAt (Immutable)

MapAt[Function[dummy, #"firstValue"], "isFirstValueTrue"]@# & /@ xx

2. Shadow (Immutable)

(<|#, "isFirstValueTrue" -> #"firstValue"|> & /@ xx)

3. Insert (Immutable)

Insert["isFirstValueTrue" -> #"firstValue", "isFirstValueTrue"]@# & /@ xx

4. QueryMapAt (Immutable)

QueryMapAt = Query[All, MapAt[Function[dummy, #"firstValue"], "isFirstValueTrue"]@# &];
QueryMapAt@xx

5. QueryShadow (Immutable)

QueryShadow = Query[All, <|#, "isFirstValueTrue" -> #"firstValue"|> &];
QueryShadow@xx

6. QueryCreateColumns (Immutable)

QueryCreateColumns = Query[All, <|"firstValue" -> "firstValue", "isFirstValueTrue" -> "firstValue"|>];
QueryCreateColumns@xx

7. Dataset[queryMethod] (Immutable)

xxDataset = Dataset@xx;
queryMethod = RandomChoice[{QueryMapAt, QueryShadow, QueryCreateColumns}];
Row[{xxDataset, " -> ", xxDataset@queryMethod}]

8. MyReplacePart (Immutable)

C2Query = Query[All, "isFirstValueTrue"];
C1Query = Query[All, "firstValue"];

MyReplacePart[C2Query -> C1Query]@xx
    
(* definition follows of MyReplacePart *)

---

9. SetPart (Mutable)

 xx[[All, "isFirstValueTrue"]] = xx[[All, "firstValue"]];
 xx

10. QuerySetPart (Mutable)

Restore@xx;
QuerySetPart[C2Query, C1Query]@xx;
xx

(* definition follows of QuerySetPart *)

11. ReplacePartFix (Mutable)

Restore@xx;
ReplacePartFix[C2Query -> C1Query]@xx;
xx

(* definition follows of ReplacePartFix *)

Comments:

1. This is essentially @Leonid's recommended, immutable solution (slightly modified into a keyless operator-form with a dummy variable that simultaneously reflects this inner function's purpose while removing it from the outer function's clutches). It is very general in the sense that MapAt can be used in more powerful ways (that does something beyond returning a constant), can be applied to any position, supports the standard "immutable" idiom and represents a way of conceiving operations that IMO is indispensable in effectively working with associations.

On the other hand, perhaps an "immutable, ReplacePart intent" or "mutable ReplacePartFix intent" more closely capture the OP's original intent.

2. This is @WReach's solution and is perhaps the most elegant one for this specific question as it leverages Mathematica's automatic overriding. On the other hand, the overriding conceptually involves a two-step process that perhaps only merits a single step.

3. Similar in tone to the previous solution with the insertion overrides the value in two steps.

4-6 These solutions represent query forms of the previous immutable solutions with All essentially replacing Map's operation. It also emphasises that while the Query hints at a passive "querying" of a Dataset/Association's content, the inclusion of transformative functions as possible operators (i.e. in addition to Part specifications) demonstrate their greater power and possibly representing the optimal way to immutably transform datasets. Its advantages are at least threefold: 1) encapsulation for improving code readability 2) harnessing Dataset's functionality 3) Extensibility from subsequent Query modification/composition. Of these I regard the last as being the most important (as illustrated shortly).

7. Dataset offers its own advantages including a visualisation produced from any of the previous queries.

8. In my opinion, this represents the most natural way of implementing the OP's "immutable intent" (i.e. if still in the "experimental or prototyping phase"). It requires first defining MyReplacePart

MyReplacePart[q1_Query -> new_] := 
  Function[assoc, Module[{temp = assoc}, temp[[Sequence @@ q1]] = new; temp], 
   HoldAll];

MyReplacePart[q1_Query -> q2_Query] := 
  Function[assoc, 
   Module[{temp = assoc}, temp[[Sequence @@ q1]] = q2@assoc; temp], HoldAll];

Note:

• This extension implements an operator form via pure functions (instead of using Subvalue given its HoldAll limitations)

• Implementing (an immutable) MyReplacePart effectively involves a inefficient, mutable detour through a local, temp variable in order to avoid changing existing state. A native implementation would naturally be faster and possibly further enhanced with a post-fix short-form (say xx |. C2Query -> C1Query)

• As characterised by all "immutable implementations", the entire data structure is returned without altering xx's underlying definition. If the OP's intent was instead to alter this underlying definition then all the immutable solutions need a concluding assignment as in: xx = MyReplacePart[C2Query -> C1Query]@xx

On the other hand, if the OP's intent was instead to alter the underlying data structure (say following a period of extended experimentation), then this can also be performed mutably which in such a context is, I would argue, the more natural approach and is used in the next three solutions.

9. This is @Leonid Shifron's (first) mutable solution using Part and Set and has the virtue of perhaps most closely following the OP's intent in a "post-experimental" phase with existing built-in functions. It strikes me as a reasonable approach for this situation or indeed any other one in which an individual and isolated change to a large data structure is required.

10. Given the previously stated advantages of Query, the previous Part-Set can be similarly cast.

QuerySetPart[lhs_, rhs_] := Function[assoc, assoc[[Sequence @@ lhs]] = rhs@assoc, HoldAll];

Note also since "mutable" solutions changes xx's underlying definition from now on this needs to be periodically Restored to test new solutions.

11. In my opinion, this solution represents the most natural way of implementing the OP's "immutable intent" (i.e. if in the "post-experimental" or "post-prototyping" phase). MyReplacePartFix is the mutable version of the immutable MyReplacePart since the underlying association, xx, is now changed in place (and hence no "conceptual copying" is needed via a temp variable).

MyReplacePartFix[q1_Query -> new_] := 
  Function[assoc, assoc[[Sequence @@ q1]] = new; assoc, HoldAll];

MyReplacePartFix[q1_Query -> q2_Query] := 
  Function[assoc, assoc[[Sequence @@ q1]] = q2@assoc; assoc, HoldAll];

MyReplacePartFix[ls_List] := 
  Function[assoc, Scan[(MyReplacePartFix[#]@assoc) &]@ls; assoc, 
   HoldAll];

Consequently, I see Dataset/Association's value stemming from its ability to combine immutable/mutable approaches - the former to perform the familiar tinkering, experimenting, prototyping and the latter to bed down any findings/breakthroughs by recording incremental improvement in those computational units of special utility or interest.

Let's flog this example one more time to envisage a possible workflow that combines both approaches:

A Toy Workflow

The OP mentioned in a comment that his real point of interest was to record an integer's size relative to 5 which can be cast as a Query:

MoreThan5Query = Query[All, MapAt[Function[dummy, #"firstValue" > 5], "isGreaterThan5"]@# &];

Let us suppose that we would like to record an application of this query together with the earlier truth/table data. Hence we restore the original xx, generate data for MoreThan5Query and use Dataset to illustrate

Restore@xx;
yy = Association["firstValue" -> #[[1]], "isGreaterThan5" -> #[[2]]] & /@ Thread[{RandomInteger[10, 4], ConstantArray["?", 4]}];
datasetShow = Map[Dataset, #, {0, 1}] &;
Row[{
   <| "Truth" -> xx, "Size" -> yy|>, " -> ",
   <| "Truth" -> QueryMapAt@xx, "Size" -> MoreThan5Query@yy|> // (base = #) &
   }
  ] // MapAt[datasetShow, {{1, 1}, {1, 3}}]

The second dataset contains the second column's agreement and for the toy's sake we'll assume that it represents a relatively stable data structure worthy of recording - as indicated by assigning it to a base variable. Suppose in addition, that after a period of time, the first columns of base need adjusting but also to remain in agreement with the second column - hence the previous queries need to be-run. But this is where we get the payoff from the previous casting in this new context.

{C1QueryT, C2QueryT} = Prepend["Truth"] /@ {C1Query, C2Query};
 C1QueryS = Prepend["Size"]@C1Query;

Now suppose the adjustment involved negating the Boolean "firstvalue"s and adding 3 to the numerical "firstvalues. The adjustment can be initially performed before the corresponding agreement with the second column is readily re-implemented.

Row[
  {
   MyReplacePartFix[
     {
      C1QueryT -> (Not /@ C1QueryT@base),
      C1QueryS -> 2 + C1QueryS@base
      }]@base,
   " -> ",
   MyReplacePartFix[
     {
      C2QueryT -> C1QueryT,
      Query["Size"] -> MoreThan5Query[Query["Size"]@base]
      }]@base
   }
  ] // MapAt[datasetShow, {{1, 1}, {1, 3}}]

A native extension of ReplacePart/ReplacePartFix or equivalent would naturally make this more efficient (and the use of the inner base could be removed) and in more realistic examples would also involve at this step, (hopefully) high-level implementations of version control and unit tests, but taken together they form a powerful way of building on the language's immutable character.

As rightly pointed by @Murta in the comments of a previous question seeking to summarise cheat-sheet learning pathway for data science functionality, one glaring omission was coverage of methods for their (mutably) modification. This functionality will hopefully now rapidly mature (it would also be useful exercise to collate the above into a complementary cheat sheet on List/Association/Dataset modifications).

A final note on mutability/immutability

The Mutability/Immutability dichotomy emphasised on StackExchange (largely contributed by Leonid Shifrin) is particularly interesting since viewed on a broader level I think it captures opposing/complementary forces that in many ways define scientific progress - experimentation and accumulation.

The Wolfram Language has long been an extremely powerful experimental platform by facilitating rapid algorithmic (and interface) prototyping. This is due in no small part to the language's immutability and all the accompanying well-documented advantages - advantages, happily, that have been continued with the recent datasets/associations additions. Following experimentation and/or prototyping however, there comes a point where one needs to play computational favourites and/or aim to permanently classify - to pick out those experiments (structures) worth recording and it is here I'd argue that a mutability idiom becomes the more natural approach - the ability to seamlessly augment a fixed structure.

In my view Mathematica has been less than stellar in accommodating mutable idioms which is also connected with it hitherto being inadvisable to use it as a platform for storing/publishing computational research. The absence of this capability also lurks behind previous, countless questions on emulations of structs/object-orientation/databases and the frustration expressed about building sophisticated and rich interfaces beyond the complexity of Manipulates.

My hunch however, is that this is all set to change followngDataset/Association's introduction since, while maintaining the familiar ability to integrate an immutable programming model, there remains the potential to incorporate mutable idioms (as it relates to the ways code is conceived and perceived - since, as pointed out, true general reference/ pointer semantics are not in place).

This is reflected initially, in the almost exclusive use Part to express mutability, in ReplacePartFix above, in and in many other StackExchange questions (including speculation about high-level front-end editing of Dataset/Associations).

I have re-visited several old dynamic interfaces originally abandoned as they sank in a spirit-sapping morass of complexity. What I have found quite remarkable is how re-implemented within a (base) Association, their growth is not merely more amenable but actually becomes feasible - the addition of the 100th feature now roughly the same level of difficulty as adding the 1st.

Consequently, rather than view mutability as a poor cousin to immutability I see it as a rich uncle needed at a different (concluding) stage of development/experimentation. In fact, I'd anticipate an environment allowing seamless switching between the two as being especially powerful with far-reaching ramifications.

Language has an uncanny knack of hiding things in plain sight and the point expressed here appears in the descriptors dataset vs database. The set embodies the familiar (list) immutable approach whereas the base in database connotes a more fixed structure with a notional fixed address that one typically wants to modify "in-place" (and whose file-backed manifestations will IMO really see data science in Mathematica come into its own).

In life, this balance between fixed knowledge and its growth manifests in our DNA's base pairs representing the fixed knowledge of stored data and/or algorithms (protein-making instructions) with the spark plugs of its autonomous experimental engine, mutation. After performing its experimentation in the environment there comes a point where those favoured, self-perpetuating genes, need to be selected and added to the base genome. Hence, in this case the DNA takes the form of a mutable data structure (that is, with DNA considered at the species level - at the individual level DNA is more akin to an immutable structure with sufficient mutation (or re-combination) defining new identities)

This dance between fixed knowledge and its experimental expansion plays out in deeper, analogous ways in both DNA evolution and scientific progress but that is another story.