i'm going to take your word for it, that what you seek is healthy fat loss. cause 125 at 5'4" (are you a guy?) is not really fat.
but to get to your questions -
1) you can stick strictly to fish and eggs, that's fine. i don't think you should do so out of a fear of fat, though. but there's nothing wrong with fish and eggs. both are high quality sources of animal protein.
2) there's also nothing wrong with non-fat Fage greek yogurt. mark recommends a very low carb diet to people, so to keep calories up, he recommends high fat products. it's a trade off between carbs and fat.
3) 'cardio' is a bit overrated for fitness purposes, but it really depends on what routine you're actually doing. fuel too. a big reason why long bouts of cardio are discouraged in the low carb world is cause they're damn hard to do on a low carb diet! which is not to say that i think long bouts of cardio are healthy.
4) there's no need to eat every 3 or 4 hours, or according to any clock. two big meals a day is fine. four small meals a day is fine. i prefer 3 square meals most of the time, but indeed, eat when you're hungry.