Along my fire place I have pretty good gaps that allows a lot of draft into he house during winter. I was thinking of just using foam backer rods and then caulking over that to seal the gaps nicely. I assume there wouldn't be any fire hazard since the fire place does not get hot on the side of it, even though there is a heat vent. Any better suggestions on how to fix the gap?
That looks like a good solution. There's no fire hazard there (if there were, you'd also be worried about the wood). You may have to switch to something thinner at the bottom there, and use additional pieces to fill in the joints between the blocks. Something I've used with good success are lengths of foam pipe insulation; it's cheap, and you can easily cut strips of any width you like.
Given that there's no water to be blocked, if you can get the gap completely filled by the backer rod you may not even need the caulk; doing without caulk would be nice since caulk would be really hard to get off the masonry.