This thread just reminded me...I suddenly stopped playing Black 2 when I got to victory road...haven't touched it in a month, I need to get to finishing it. >.>
Anyway: If you want to use legendaries or not is up to you, but I can discuss what pokemon might be a good addition to your team at that point in the game.
Your team right now is some trouble with ground types, which are fairly common. Even your Tentacruel has a weakness to ground since it's part poison. Leafeon is the only one you have to counter them well, and Leafeon isn't really the right pokemon to do that, especially if against a defensive ground/steel type, which is your biggest problem right now and could take down your entire team if you are against a strong opponent or are under-leveled at all. I highly suggest getting a flying type, you'll want it for the ground types, and the ability to fly helps with travel immensely, although this flying type has to be able to learn a move to counter the steel/ground types.
From my experience, Tentacruel and Leafeon tend to be more defensive pokemon, so for your final triumph of ground types should be something offensive. Quilava is more special based if I'm not mistaken, and Luxray is more attack. Seeing as you're mostly balanced anyway, it might be easier to just make the easy choice of getting a flying type with a high attack stat instead of special attack, since they tend to commonly have that. Luxray and Quilava aren't the fastest pokemon, either, so a fast one would be good...although one that can take a few hits with decent defense stats might be fine.
Gyarados is a good choice, although it's a pain to train the Magikarp, and I can see why you may not want one.
Salamence is also a good one, and it satisfies the dragon type toby mentioned if you care.
Again, it's a pain to get one, though, since you need to go to the safari zone and the safari zone is already a pain with how it's set up in HG, however it can learn some good moves like Earthquake, taking out the digging ground types early on and part steel types will still feel quite some damage, while also being a flying type to completely stomp any ground type out there.
Although, a far more under-used and, in my opinion, underrated pokemon, Staraptor, can also deal some heavy damage, probably more than Gyarados or Salamence even can, although taking more damage and falling in a single super effective hit from just about anything...it learns a very powerful move, Close Combat, at only level 34, which is not too far from your current level 30s. It can deal some really heavy damage to anything weak to it, like steel/ground types that I was mentioning being a huge issue. Again, issues with getting one, though...you'll need to pick one up in diamond, since they don't become available in HG until far later in the game. (after you beat the elite four.) Luckily, they are by far one of the easiest pokemon to find and catch in diamond, being one of the first two pokemon you're likely to encounter in the wild, and even appearing many times later in the game at levels 20-30.
Edit: Oh, and if you had picked SS instead of HG, you would have been able to get Lugia, which also would have been a good choice, even though it's a more defensive pokemon, simply for the fact that it's stats are through the roof. (And because it can learn water type moves, but meh.)
Hope this helps. xD It's really long.
And yes, I'm a pokemon nerd. I know far too much about pokemon.
(Except 5th gen, I'm still hardly sure of the types of more than half the pokemon there.
)