2.  Yes this follows from the definition of a heuristic and the montonicity 
of f.

Consider any node n along any path to the goal, we have:
     f(n) = h(n) + g(n)
By definition of heuristic, which is 0 at a goal state (see p. 93) we have:
     f(z) = g(z) + h(z) = g(z) + 0
for goal state z.
We also know that the goal cost can be written as a function of g(n) as 
follows:
      f(z) = t(n) + g(n)
where t(n) is the true cost to the goal from node n.  Since f is monotonic 
we also know that
     f(n) <= f(z)
     h(n) + g(n)  <= g(z)
     h(n)  + g(n) <= t(n) + g(n)
     h(n) <= t(n)
Thus, we see that h(n) is less than or equal to the true cost t(n) to get 
to the goal and therefore as an admissible heuristic since it does not 
overestimate the cost.


3.  No, the new algorithm does not achieve the same O(n^2) performance.

Consider the following statement in CNF:
         (a or b) and (~a or ~b)

      with initial truth assignment:
          a = true;
          b = true;

      We can see that the first clause is satisfied but the second is 
not.  The algorithm will therefore select the second clause and flip all 
variables in this clause resulting in the assignment:
         a = false;
         b = false;

     We can see that this clause in now satisfied, however now the first 
clause is not.  The algorithm will flip its variables resulting in the 
original assignment:
         a = true;
         b = true;
Thus we can see the algorithm is in a loop and will never find a correct 
assignment although one exits:
         a = true;
         b = false;
Therefore we know that the algorithm cannot find satisfiable assignments 
with probability going to 1 in O(n^2)