How many level 4s are you talking about? That makes a big difference in the scale of the encounter.
You can, of course, also use the class templates in the
DMG to add PC powers to existing creatures -- there's a whole lot of surprises there -- PC powers tend to be pretty kickass.
But,
IMO, your problem isn't really going to be solved by templates, I don't think. It's tough to challenge a very tactically astute group -- especially one that knows the books backwards and forwards.
Start looking for combinations of terrain and creature that packs a lot of punch -- and really use the environment to make life complicated for the party. One of my first TPKs with
4e was an encounter in which I combined (among other stuff) a howling hag and an elite daggerthorn briar. Combine the serious stopping power of the briar with an opponent that can push the PCs into the reach of it, and you've got a reciept for a whole lot of hurting.
The primary idea of a template is that it gives you a structure for creating a longer-lasting, more resilient and possibly more interesting adversary. The whole
4e philosophy, though, is that you don't need to worry about doing that sort of development "by the numbers". So long as you can sleep at night, and your players are having fun, you can pretty much do anything you want to them (so long as it stays fun).
This is one of the changes in the system that is hard to put into books -- it's sort of woven into the genetic code of the game -- there are guidelines for making your monsters up yourself -- some numeric guides for what they should do -- but what I really recommend that you do is stop looking for something you can plug in, and start thinking about what would be cool and surprising to your ubermensch.
One last thought -- one I forget from time to time as I'm desigining stuff for my groups. The PCs are supposed to win (just about) every single time -- and nailbiter combats actually stand out better if there are a handful of not so stressful combats surrounding them -- if every combat is a knife's edge from
TPK, that probably means that players aren't having as much fun as they might -- there are cool abilities and fun things to do that players won't do in combats that are right out there on the bleeding edge. Slightly easier combat can give them license to be a bit more cinematic and wild from time to time.
-j