Looking at it from a "CR budget" stand point is fine and dandy, but as we are all aware CR isn't always the most accurate depiction of difficulty (though admittedly this is much less pronounced at low levels).
Look at it this way.
First, go to Kobold Fight Club and isolate CR12 monsters.
Then remove everything with a legendary action and legendary resistances, because the outcome of those fights will be clear. Barring some extraordinary circumstances, the monster with legendary actions will stomp the L4s. For example, a pair of L4s aren't about to reasonably fight an Int 19 Ki-Rin that can throw out a Holy Word and then take 2 legendary actions to either move 60ft, or throw out free 4d8 damage sacred flames.
A level 4 Barbarian with 16 Constitution and fixed stats has 45 HP. That's probably going to be about as good as it gets for HP at level 4. A chain lightning or an up-cast Cone of Cold will probably do that much damage. Fireball damage is comparable. Not to mention that, if the monster is a high-level caster, it's probably smart enough not to reasonably let a bunch of L4s get the upper hand on it. So, you can also remove all of the casters with access to level 5+ AoEs.
You are not left with many options. I suggest that the easiest of these is something like the Gray Render or a Frost Giant Everlasting One, either of which is likely to drop a PC each round. I would say that the Gray Render is likely the easier of the two, so let's go with that.
The Gray Render has 19 AC. It gets 3 attacks, 2 of which prone at DC16, doing something like 54 damage/round. However, it's a large dumb brute with a 30' move speed and can probably be CC'd relatively easily via an intelligence or Wisdom save (i.e. - Phantasmal Force) and worn down over time at range. It's conceivable that something like a duo of casters could beat it under the right circumstances. Similarly, a duo of optimized ranged characters (say, L4 Variant Human Rangers with Sharpshooter and crossbow expert, or PCs with a fly speed) could also kite it and whittle it down if they fought it in an open field.
Apart from this, the PCs' advantage would have to be extreme (i.e. - 2 barbarians inside an cage inside an anti-magic field vs an Archmage), in which case the monster probably wouldn't be fairly CR'd at 12.