As many others have suggested, server restart.
I've tried it, and was never successful. Unless your server is the first to come up out of all those included in your CRZ, the Minfernals will be long gone before you can even load into Felwood.
What I did was camp for about four hours late at night/early morning.
I ran around and killed every non-Minfernal battle pet in the area, in hopes that it would trigger a Minfernal to spawn. I have no idea if that worked, but in the end I nabbed one. Only one Minfernal spawned during the entire time I was there.
Another trick that might help is if you have a friend or a second account, take a toon over to Felwood and park it in the area. The more a zone is populated, the higher the chance of more/faster pet spawns.
Minfernal is a somewhat special case, though, so it's hard to say if these tactics will really improve your chances. From personal observation, killing other wild pets did cause other wild pets to spawn faster (but not sure if that helped the chances for a Minfernal), and when the Minfernal finally showed up there were at least three other players in the area with me.
Feel free to browse through Perks N Peeves
, my vanity pet collecting blog!