Seras Victoria from Hellsing. In a world of Black and Grey Morality, she seems to be the lone wide-eyed idealist in the series. She also possesses vampiric super strength and is more than capable of wielding guns far too large for any human to handle, taking out mooks with her bare hands, and grinding off the heads of those who piss her off.
Tower of God: Mule Love, who looks like a little boy in overly baggy sports wear. He is about a hundred times stronger that your average Badass Normal.
Akane Tendo from Ranma One Half. Everyone who falls for her talks about her charm and grace and femininity and cuteness. They ignore the fact that she can shatter concrete walls with one punch or defeat groups of armed men with her bare hands. She also regularly punches Ranma a significant distance, and has effortlessly kicked a large metal globe like a football over a field.
Anime Chinese Girl Shampoo is strong enough that she can walk through walls (no, not phasing- simply smashing through concrete, wood, whatever with all the nonchalance of someone walking through an open door) and skilled enough that she can handle Akane Tendo with ease. In fact, her tendency to leave a trail of wreckage in her wake (walking in a straight line between points A and B, no matter how many walls or houses she has to plow through to get there, for example) might less be her unable to fully control her strength and more her being a Jerkass who knows she's got Super Strength and wants to show it off.
And then, of course, there's also female Ranma - a girl probably no taller than five feet, and yet has managed to obtain almost stupidly high levels of Charles Atlas Superpower...
The adorable, energetic Yachiru is the vice-captain of the 11th Division of Soul Society's thirteen court companies, capable of lifting her superior (himself a fairly large individual, a bit over twice her height and probably 8-10 times her weight) and leaping tall buildings with him in tow, apparently not affected in the least by the extra weight she's carrying over her head. She is also capable of emitting a frightening Battle Aura when angry. She has the appearance of about a 7-year-old girl.
The meek Ururu Tsumugiya is strong enough to beat up Soul Reapers, and when she fought Ichigo (after asking him to wear large amounts of padding), she nearly punched him through a mountain. She even has a danger mode where she enters a trance and seems to go into automatic pilot to kick hollow ass. Unfortunately, this trance doesn't seem to be able to respond quickly to fraccion transformations. She also possesses a giant bazooka that's larger than she is.
Hiyori Sarugaki, Vaizard and erstwhile vice-captain to Shinji Hirako, delights in hitting people with her sandal, kicking people in the face, and labeling her cohort and former CO a "dickhead". She's also about as high as your knee and has the appearance of a towheaded, foul tempered elementary schooler.
As a kid, Simon is also implied on several occasions to be very strong, most notably in the Hot Springs Episode when he manages to lift six-feet-tall-or-so, muscle-bound Boisterous Bruiser Kamina on his shoulders without any trouble. This is despite his being two heads shorter than Kamina and a great deal skinnier. Though Rule of Funny applies to that scene as well.
Keep in mind that Simon used to spend most of his days digging around underground. He uses a large hand-operated drill to dig with and doing this surely requires tons of strength and stamina. Despite his appearance, it's possible that Simon is just as strong, if not stronger, than the muscular Kamina.
Compared to the many Amazonian Beauties that populate her class, Ku Fei from Mahou Sensei Negima! is positively tiny, yet she is respectfully referred to as "Chairman" by numerous male martial artists for her fighting prowess. Also gains extra cuteness points for being The Ditz.
And on the male side, we have the lead character himself, his friend Kotaro the wolf boy, and (though "cute" may not be the right term) the apparent Big Bad Fate Averruncus aka "Tertium" the Third. Each is an Adorably Precocious Child, and they are some of the best fighters seen in the series so far.
Robotic character Chachamaru is a Huge Schoolgirl normally, but she has two body types that are much more lolirific in design without losing the Super Strength.
Birdy the Mighty has already been known as a BadassAction Girl, but what's surprising is that she has been that even at such a young age. The second episode of the second season has a flashback of her confronting an evil monster and tearing off its arm! During her childhood!
Pan in Dragon Ball Z/GT. She was cuter in DBZ, but more of a bruiser in GT.
Her grandma, ChiChi, in the original Dragon Ball and her mom, Videl, from Dragon Ball Z also count.
The child versions of Goku and Krillin from the original Dragon Ball (and Goku in GT) may or may not count, depending on your definition of cute.
Then we have to add Gohan, Goten and Chibi Trunks. And maybe even Gotenks?
Really, it pretty much runs in the Son family.
Post-timeskip Sakura from Naruto. While she's primarily a Combat Medic, she makes use of her chakra control skills by building up chakra in her fists and releasing it all at once. She first demonstrates this ability by smashing the ground open.
Early in the series manga, she picks up her partner, throws her over a wall, and runs and jumps fast enough to catch her on the other side. Exasperated teachers (this was supposed to be a lesson in teamwork) made her do it over. We thought this super power was just the Rule of Funny. It was actually foreshadowing.
Einhart Stratos is this in Magical Girl Lyrical Nanoha ViVid. Her child form is completely average size for her age and her adult mode is rather petite, despite this, she still is able to knock around Nove, someone who can give Subaru a run for her money in a one-on-one fight, with ease.
Rio, from the same manga, is also one, simply by the fact that she's the most petite of all the characters and can smash a Golem in one hit.
Nuriko in Fushigi Yuugi. A slender, effeminate crossdresser, whose particular ability happens to be ridiculous wall-smashing superstrength. Halfway through the series he gets an upgrade in the form of magic gauntlets that make him even more powerful.
Shinobu from Urusei Yatsura, whose super-strength evolved from sight gag to full-fledged super-power.
Though Shinobu later gets bumped to second place in strength by Asuka Mizunokoji.
Hifumi from Koi Koi 7. She's perhaps the most childish of the team, yet packs the cyborg ability of super strength.
Excel Excel of Excel♥Saga may be a parody of this trope. Though she's just out of high school when she joins ACROSS, she's been known to beat the holy living hell out of entire armies with only bare fists and sheer force of hyperactivity. She's also apparently completely immune to the Puchuus' cuteness.
Also Ropponmatsu #2, a robot girl designed to look like an adorable and sweet young girl because of her creator's... um... preferences. She's a cute cat girl yet she can punch a cyborg through a brick wall.
Allenby from G Gundam is a teenage girl who kicks just as much ass as the rest of the kung-fu battling protagonists.
And Sai Saici is 16, looks around 12, and is just as much of an asskicker as Allenby and the older, more experienced Shuffle Alliance members.
Brock's Happiny from Pokémon: she's been seen lifting boulders, several cement blocks and her own trainer over her head.
She's now lifted an entire frozen lake and chucked it into an abyss. No really.
In the games, Happiny is tied with its evolution, Chansey, for having the lowest physical strength of all Pokémon. Talk about irony.
Also, Badass Normal Li Meiling. And heck, Shaoran counts as a male version, and there's Sakura as well when she uses "The Power"...
There's another non-female example in One Piece that nonetheless fits this trope pretty well: Zoro as a 11-12 year old. He was beating up adults before he was old enough to shave, but in the anime version of the story, he was also arguably insanely cute. (Admit it. If you're female of childbearing age, you probably squealed like mad whenever Tiny!Zoro came on-screen.)
And Kuina, the straightforward female example of this trope.
Luffy, Ace and Sabo as children. Well, Sabo never got a chance to be anything more than a Cute Bruiser.
Emily Adachi from Air Gear has insane strength. For a while, her physical strength was equal to if not greater than that of the team's initial heavy-hitter Buccha. In fact, she had above average strength even before getting into Air Trecks. At one early point, FOUR girls try to beat her up for being too friendly with Kazu (whom their leader had a crush on), and she thrashes the lot of them in a matter of seconds.
Another male example: Kintarou "Kin-chan" Touyama from The Prince of Tennis. Tiny, not very bright, cheerful, adorable, friendly... and with an absurd degree of Super Strength.
Though he is supposed to be some sort of urban-yet-wild young Tarzan, and if anyone remembers the movie, Tarzan was insanely cute (and bruiserious) as a kid, too.
Hungary from Axis Powers Hetalia, when young. She grew into a Ninja Maid. Also, a male example is Chibitalia aka young North Italy... in a single strip.
Arguably, child!Prussia and child!Switzerland are other male examples.
Finland also qualifies. Until the Winter War, you'd think his fighting skills were just an Informed Ability...
Definitely Chibiamerica, the two-year-old who can swing a bison by its front hooves. And he never really grows out of it. It being a moe anime, and all. I mean, come on, cheerfully dragging a car over to its owner to ask if he can borrow it? Cute bruiser.
Claymore's Priscilla post time skip, is more powerful than the abyssal ones. Just to put that into perspective, the Abyssal ones are the manga's equivalent of physical gods
One of Mamoru's classmates in GaoGaiGar has far more strength than she should logically have. She doesn't have superpowers or anything-but when three other classmates are falling from a window, she's strong enough to not only hold but to pull back up the entire group. It's pretty much just a comic relief device, however, as with most of the classmate interactions.
Mio from NEEDLESS. She may look like just a cute, pink-haired girl with a teddy bear (well according to her it's a bunny), but both she and the bear pack enough strength to take down some of the most powerful characters in the series.
Gouriki Banchou from Kongou Banchou, although quite small in comparison to everyone else (except the little kids), has a "hyperion constitution", which basically gives her superstrength and a super defense - she carries around two iron balls on sticks that are far larger than she is as her weapons, and when she lands on spikes sharp enough to pierce her weapons, they bend, leaving her unharmed.
A male example is Astro/Atom from Astro Boy/Tetsuwan Atom. Sweet, innocent, and adorably babyfaced - and absurdly strong.
Slightly subverted in that his sister Uran, despite being smaller and female, is less powerful - though one might argue that she still qualifies.
Lirin from Saiyuki is a prime example, where even though she's a young teen with the ability to punch a hole through the gut of a 3-story giant monster crab, the main heroes still underestimate her repeatedly due to her cutesy personality. Generally considered the series' female counterpart to Son Goku, who is to all extents and purposes a god (and a Cute Bruiser in his own right).
Pai from the almost forgotten 3x3 Eyes is a classic anime example of the girl who's happy being a cute, innocent little waif one moment, while running around and dispatching/vaporizing demons with her bare hands (granted, that petite little frame houses overwhelming mystical powers, not to mention a split personality) and behaving in a totally cynical, badass manner the next.
Shiratori from Pani Poni Dash! is a bit taller than the average cute bruiser but she is cute - and has a hand chop that has an impossible amount of power behind it. In one episode she applies a "wake up chop" to a sleeping Himeko and imprints her face into the metal plate at the bottom of the desk.
She's known by the nickname "Palmtop Tiger", a name that means "Small, but vicious". Like Ryuuji says during said meeting, it fits her perfectly.
Wendy from Fairy Tail, especially during the Edolas arc.
Piss off Mirajane and you're boned!!
Kaoru Konoe from Gate Keepers. While most of the cast look ordinary enough except for their Gate powers, Kaoru fits the trope best. As keeper of the Gate of Pursuit, she can enhance her physical abilities to superhuman levels, with all the cliches that implies.
Vividred Operation has two cute and heavy beaters: Aoi, a shy girl whose weapon is a hammer double her size, and Himawari, a computer hacker who uses giant Deflector Shields as her weapons. They both have similar roles in combat: breaking barriers and repeling attacks with sheer forces.
Mikasa from Attack on Titan. While she looks pretty, delicate, and demure, she is fucking terrifying when she needs to be.
Eve from Black Cat. She has nanobots that change when she wants to, effectively a shape shifter