I would use Photoshop for this.
1) Place the image layer below the color layer. Toggle the eye/view on the color layer to make it invisible.
2) Using the wand tool, or any way to selection tool (lasso, quick selection), select the parts in the image you want to remove from the color layer. This can be done is parts if necessary.
3) After the selection is made click back on the color layer, toggle it so that it is visible, and hit delete to remove that selection from the color block allowing the image to show through.
This can also be done with the eraser if you prefer the brush tools. Just layering the color layer above the image layer, lowering the opacity of the color layer so you can see through it (opacity is top right in the layers panel) and erasing the areas you want to show through. Later when you raise the opacity the color layer only what you've eraser will show the behind image.
Hope this helps!