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:
vincent2 quickCount: 0.255000
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 with respect to the input list.
The better solution
So I finaly mangaged to get handling Tally's output fast enough to make it faster in the given example usage case:
quickCount[data_]:= Map[Tally[Join[{1, 2, 3, 4},#]] &, data][[1 ;;, 1 ;;, 2]] - 1
vincent2 := quickCount[myData]
The unspoken detail is ofcause that this has a different output format, and to put it back into the same output format it becomes slower then the above, eg:
Transpose@{{1,2,3,4},#}& /@(Map[Tally[Join[{1, 2, 3, 4}, #]] &, myData][[1 ;;, 1 ;;, 2]] - 1)
runs in 0.314031 for the test.
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