Seeing as my initial comment seems like a both elegant and fast solution I'll post it as an asnwer. Basically it's just using `Outer` to carry out the same sort of loop you wrote in the last part of your question:

    Outer[{#2, Count[#1, #2]} &, myData, {1, 2, 3, 4}, 1]

I honestly didn't expect it to be faster than solutions written specifically for this task, just though I'd mention it, since this is in my oppinion a nicer way of doing a "double map" over each element in the first list with each element in the last list. But it seems to be acceptable when comparing speeds with the other posted solutions.

Timing this and the other solutions here (using `Do[code,{10000}];//AbsoluteTimin`), I currently get the following timings:

    jVincent      Outer:  0.302000
    Andrew        myFun:  0.344000
    Leonids       myFun:  0.772077
    kgulers     myTally:  0.828083
    Mr. Wizards countBy:  0.965096

So it seems to do just fine with respect to computational efficiency. 

**For completeness**

I chose originally not to post this originally since it's just repeating the code of other answers, but since Leonid asked, here it is:

    andrewMap[sublist_] := Map[{#,Count[sublist,#]}&,{1,2,3,4}]
    andrew := andrewMap/@myData

    vincent := Outer[{#2,Count[#1,#2]}&,myData,{1,2,3,4},1];

    myFun[sublist_]:= SortBy[Tally[sublist],First]
    myFun[sublist_,elems_] := Replace[myFun[sublist~Join~elems],{el:Alternatives@@elems,n_}:>{el,n-1},1];
    leonid:=myFun[#,{1,2,3,4}]&/@myData;

    countBy[dat_, bins_] := {bins, Tr /@ Reap[Sow[1, #], bins, Tr@#2 &][[2]]}\[Transpose] & /@ dat
    wizard:=countBy[myData, {1, 2, 3, 4}];

    myTally[data_, elems_:{}] := Composition[# /. {e_, n_} :> {e, n - Boole[MemberQ[elems, e]]} &, Sort, Tally, Join][#, elems] & /@ data;
    kguler := myTally[myData, {1, 2, 3, 4}];

    Do[vincent, {10000}]; // AbsoluteTiming // First
    Do[andrew, {10000}]; // AbsoluteTiming // First
    Do[leonid, {10000}]; // AbsoluteTiming // First
    Do[wizard, {10000}]; // AbsoluteTiming // First
    Do[kguler, {10000}]; // AbsoluteTiming // First