Of course it's a challenge! Yes it's time consuming, but still a pretty good challenge completing the game with a level 8 Cloud and a level 7 Tifa.

I think it's definitely possible to get Cloud to learn Omnislash at Level 8. I am sure the kills he makes in battle will count towards his total even if he dies in the fight. I'm 99% sure on that. I don't think it would take that long either. Go to the Mythril Mines or some other place where large groups of enemies gather and have Cloud kill them all off, before killing himself and have a higher level character finish the fight.

Actually a better tactic may be to fight enemies who's levels are divisible by 4 as you could then use Level 4 Suicide on them and then Cloud should be able to finish off the enemies just with attack even at level 8. Luckily enemies who's level is divisible by 4 tend to hang out in the same places such as the Great Glacier, near Cosmo Canyon and near Wutai.

As for winning Omnislash from the battle arena, you could use one of your characters at a higher level, however it is still very possible to win both the normal battle square and special battle square types at Cloud's lowest level. Using Enemy Skills such as Level 5 Death, Bad Breath and Frog Song will be very useful as will items. There are videos on youtube of GarlandtheGreat winning the Special Battle Square at Level 8 with Cloud...not that you have to even do that to unlock Omnislash, but yeah.

Good luck!