It's possible with a regex. Here's one spectacularly awful way: enumerate through all the permutations of 3 out of 4 character classes. Assume the classes are A, B, C, and D just to simplify the syntax here:
Well, they wanted 4 of 4, actually, and yes, I had to do custom validation. Everything except the upper-case character worked in JS, so everything "just worked" if I took that part out, but that wasn't an option.