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.
Akane Tendo. 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 Kusajishi 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, Visored 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.
Meninas McAllon, aka "Sternritter P aka The Power", is the rare evil example of the trope. She looks like a highschool student, wears her hair super long and has a very frilly uniform... but her fighting style involves things like her lifting an enormous chunk of a street, including the lower foundations and at least three buildings, and throwing it down effortlessly at her enemies. She's even strong enough to paralyze Kenpachi.
Misaki Yata of K. He looks like a kid - an easily excited, blushing, skateboarding kid. So it's easy for opponents to underestimate him - until he shows them that he knows what to do with that baseball bat. The flame powers help, too.
Neko also qualifies—while she's mostly known for her perception interference powers, she's a proficient hand-to-hand fighter as well. (Well, more like foot-to-face fighter.)
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 an Action 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.
The two girls from the original series will take this trope to the extreme. Then we have the "Mistress of the Night Sky" in the next one.
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 even lifted an entire frozen lake and chucked it into an abyss.
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. Or so we thought.
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.
Kyouko Iwase can be potentially a Cute Bruiser driver too.
Hungary from Axis Powers Hetalia, when she was young. She grew into a Ninja Maid. Also, a male example is Chibitalia aka young North Italy, who defeats the Ottoman Empire with presumably nothing but a longbow at one point.
Finland also qualifies. Until the Winter War, you'd think his fighting skills were just an Informed Ability... He's actually a rather fearsome Friendly Sniper. At another point, he's so disappointed when Sweden calls off a battle with Lithuana and Poland that he cries and drowns his sorrows.
Definitely America, who as a two-year-old who could swing a bison by its front hooves. And as an adult, he Megaton Punches one of the Pict in The Movie, sending it flying. Not to mention him cheerfully dragging a car over to its owner to ask if he can borrow it? Cute bruiser.
Japan, who despite his very youthful appearance beats the hell out of the Parallel!France that tries to attack him in the 2010 Bloodbath with a rolled up poster.
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 Kongoh Bancho, 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 3×3 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.
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.
Arale from Dr. Slump is a tiny Robot Girl who's more than able to punch adults of all kinds without any efforts.
The lovely lady in the main page image is Ookami Ryouko of Ookami-san to Shichinin Nakamatachi. Despite her flat & slender figure, she can easily take on thugs thanks to her training in boxing.
In Hayate the Combat Butler, Hinagiku Katsura is best known for being the pink-haired, romantically-clueless, and incredibly cute Student Council President that often has her rather flat figure mocked...as well as being the Kendo Team Captain and one of the only characters that can keep up with Hayate's athleticism and combat skill. She may not have Hayate's Made of IronUp to Eleven (probably), but Hayate trusts her to back him up without worrying about her (too much anyway) since not much can face up to her in melee combat, especially once she breaks out the magic swords.
Mio Naganohara of Nichijou. While she is generally a nice person, whatever you do, DO NOT piss her off, or bad things WILL happen.
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.
Several of the women from Attack on Titan. Mikasa Ackermann, Annie Leonhart, Krista Renz, and Petra Ral are all small, adorable-looking women..... but are also accomplished soldiers capable of killing a 15 meter Humanoid Abomination on their own. The first three graduated in the Top 10 of their military class of 200+, while Petra was handpicked to be a member of The Squad due to her high ratio of Titan kills.
Eve from Black Cat. She has nanobots that change when she wants to, effectively a shape shifter
The title character of Haiyore! Nyarko-san is an adorable teen girl...and also a merciless fighter who shreds Lovecraftian abominations like they're made of tissue paper. Of course, she's also the human form of Nyarlathotep the Crawling Chaos, one of the most powerful beings in the Cthulhu Mythos.
In Hunter × Hunter the two main protagonists, Gon and Killua, are two 12-year-old boys that have taken on full grown adults in battles and have won, in the Heaven's Arena Arc, both of them cleared the first 190 floors of challengers with just one hit each and they fit this trope to the letter about being cute◊.
Minako Aino / Sailor Venus of Sailor Moon and Codename: Sailor V is a short, hyperactive teenager who can take out youma with one kick, and can do the same to a brainwashed Makoto Kino. During the first chapter, we are introduced to her by way of beating up a group of boys who told her that she might not be feminine enough for her crush. In the anime, she breaks the Amazon Trio's metallic manacles, armed with only the power of pure, distilled rage before transforming into Venus and scaring the daylights out of them. All this, after she had been subjected to an excruciating Mind Rape... That appears to have turned her on.
Hibiki Tachibana from Senki Zesshou Symphogear. She can't use her gear to summon a weapon, but compensates by learning kung fu and modifying her gauntlet into a Power Fist. The result is an adorable teenage girl who can punch monsters into craters from a couple blocks away.
Black Bullet. All of the cursed children are born with the Gastrea virus in their blood and can easily manipulate the virus that will grant themselves super strength, agility, and Healing Factor. This is in turn make them valuable assets for civil security companies where they work as Initiators to fight the Gastrea monsters. And many of the said cursed children are adorable lolis such as Enju Aihara, Tina Sprout, Kohina Hiruko, and many more.