My brother was in a similar situation a few months ago. But he works away offshore, 3 weeks home, 3 weeks away which makes the situation more difficult.
To start with he got to see his daughter for 3 x 2hours a week (decided by the courts), plus whenever it suited the mum if she wanted to go out etc, but not to stay overnight, plus his new girlfriend couldn't be there.
Gradually he's getting more and more time with her and is now allowed her overnight and his girlfriend is allowed to be there.
Plus they live in Wales, i don't know if that makes any diference.