In fact, you don't really need a great story to develop a proper rom hack. You can take GameFreak's stories to follow as an example of what to do.
A dumb character born in the poorest village of your region (in terms of the number of houses and so) who receives a Pokemon by accident (R/S/E, D/P/Pt) or by the region's Pokemon Professor (B/R/Y, G/S/C, B/W/B2/W2...) Main quest is to complete the Pokedex and become the region's new Pokemon Master.
Somewhere between the first and the second medals you face the enemy team for the very first time and after that, you start interfering them until you discover their evil plan and stop them somewhere near the end of the story (7th medal for example).
The main reason that attracts people to play certain HackROMS is not always the story (which helps, is true) but the gameplay itself. If you add a bunch of new features such as Megaevolution (given to the player at some point on the adventure between the 4th and the 6th gym leader), new moves (to get up to date with current gen), new mechanics, little sidequests, a decent post-game (Battle Frontier, I'm looking to you), nice interaction with certain NPCs such as your rival or your family in the game, then you get a decent game no matter the story it has (okay, it has to be almost at GameFreak's level, but that's not difficult to get xD).
I hope this helps you to develop your own ROMHack. At last but not least important, make sure you more or less know what are you planning to project onto your project before doing anything, in order to have all your ideas set up first. Then it would be less frustrating to develop since you won't get stuck so many times trying to figure out what to add next on your game's plot :awesome: