If the group over specializes in combat then it's time to throw other challenges at them.
Environmental hazards are deadly if ignored like walking blindly into a hot desert without the right provisions. Not all challenges are combat and can be just as deadly.
Example 1: Taking a long ship voyage across the sea and some event kills the crew leaving only the party to control the ship. Does anybody know how to work a ship? Does anybody know how to navigate open waters?
Example 2: Party has to run a proving grounds to show there worth to a tribe. These grounds must be run with no equipment other then mundane gear provided by the tribe. The proving grounds can have puzzles, traps, monsters, anti-magic fields, etc. Does not have to be lethal but can be if players are careless.