Provided your ISP allows you to hook up a second router in parallel, that's a viable solution. But from what I can tell c6300 has a builtin cable modem. I'm doubtfull whether it will work connecting 2 cable modems side by side. But if you have a second cable modem/router you could always try. An another solution would be to make your phone act like an internet gateway, and connect one of the PS4 through it when playing.
Yes, the problem has to do with ip addresses. For the PS4s to get full connectivity, each needs it's own ip address. When connecting them through a router they are forced to share a single address, and that simply doesn't work very well.
Using VPN to connect one of the PS4s to a different network (work/school/friend/neighbor) would be a viable solution if the PS4 had built in support. Unfortunately I don't think it does. You would be forced to rig up a PC with 2 network interfaces, that acts like a router on one of the interfaces. It's a technically interesting solution, but a rather messy one.