Quick question - is the Rank Up system the only way for characters to gain permanent stat increases? Levels don't give me stat increases anymore (and to be honest I wasn't paying attention close enough to notice if they ever did), and my strongest physical attackers (level 80+) still barely break 1000 damage on higher level enemies. I've seen videos of players with much stronger attackers... so I'm a bit confused about my lousy damage output. I'm really struggling against the end game bosses.
Characters don't gain stats on level up (though Level itself plays an important role in damage formulas, particularly physical damage), and it all comes from the sources gained from rank-up. However, it's only half the setup; the rest comes from what equipment and Materia you use.
First thing is that Elements are important for physicals as they double the amount of damage that they can do; for instance, the Crater enemies should mostly all be weak to Holy so combining Elemental + Restore/Alexander/Revive/etc. in a character's weapon should result in 2x damage in 99% of the fights you encounter down there.
As for equipment, you'll want to lift Strength where you can with Armour and Accessories to try and get their overall attack above at least 200 or so.
An Ultimate Weapon will also greatly boost physical damage, as these use special modifiers based on enemy level, HP, MP, stuff like that. You can also boost your critical hit rate by buffing Luck where possible; Amulet gives a huge boost to this stat.
And on Materia, you'll want to try and stack counter-attack, get Multi-Cut, Added Cut, Command Counter + Mug/Deathblow, anything you can to up your output of attacks. Physical attacks tend to hit less than the strongest-tier spells, but they can be made to hit a lot more often.
I guess the last thing is to try and avoid using back-row if you have a short-range physical attacker and avoid using Sadness as these restrict the number of Limit Breaks you can throw out. But as this leaves them more vulnerable to incoming physical attacks, it'd be a good idea to have some protection up like Barrier or someone tankier who can Cover them.