You can still use your original strategy, just add a list of unique elements you wish to track, to your sublists, and then adjust the counts. You can add a second definition to your original `myFun`, which would take a list of tracked elements as a second parameter, as follows:

    ClearAll[myFun];
    myFun[sublist_] := SortBy[Tally[sublist], First]
    myFun[sublist_, elems_] :=
      Replace[myFun[sublist~Join~elems], 
         {el : Alternatives @@ elems, n_} :> {el, n - 1}, 1];

Then, 

    myFun[#, {1, 2, 3, 4}] & /@ myData

produces the result you desire.

**EDIT**

Since the performance issue came up, I have to mention that the above solution is suboptimal, but not due to `Tally`, but rather due to the use of `Alternatives @@ elems`, which makes its complexity to be `O(Length[elems] * Length[sublist])`. Here is a much faster one:

    ClearAll[myFun1,leonid1];
    myFun1[sublist_, elems_] :=
       Module[{tallyT = Transpose@Tally[elems ~ Join ~ sublist], 
          range = Range[Length[elems]]},
          tallyT[[2, range ]] = tallyT[[2, range ]] - 1;
          SortBy[Transpose[tallyT], First]
       ];
    leonid1[dat_, bins_] := myFun1[#, bins] & /@ dat

from what I could see, it is the fastest so far. I save big because I put `elems` in front, and so, since `Tally` does its counts in the order it meets the elements, I know precisely the positions of elements where I need to adjust the counts. And I sort the result afterwards.