This problem is discussed in the ["Handbook of Linear Algebra"][1] book:

> When standard linear algebra methods are applied to matrices containing symbolic entries, the user must be aware of new mathematical features that can arise. The main feature is the discontinuity of standard matrix functions, such as the reduced row-echelon form and the rank, both of which can be discontinuous. [...] The recommended solution is to use
Turing factoring (generalized PLU decomposition) to obtain the reduced row-echelon form with provisos.

I don't think that the ["Turing factorization of rectangular matrix"][2] is implemented in Mathematica (it seems to be the case for Maple and Matlab). You can always settle on a upper-triangular form from the plain LU decomposition, which does not make assumptions such as those made by the `RowReduce` function:

    m = {{aa, bb}, {cc, dd}};
    n = Length[m] (* == Length[Transpose[m]]*)
    {lu, p, c} = LUDecomposition[m];
    (u = lu  SparseArray[{i_, j_} /; j >= i -> 1, {n, n}]) // TableForm

    (* sanity check *)
    l = lu SparseArray[{i_, j_} /; j < i -> 1, {n, n}] + IdentityMatrix[n];
    m[[p]] == l.u

NB: a very similar question was already asked [here](http://mathematica.stackexchange.com/questions/16279/rowreduce-problem.) (duplicate?).

  [1]: http://orion.math.iastate.edu/lhogben/HLA.html
  [2]: http://doi.acm.org/10.1145/271130.271135