I would take one regiment, work out the losses for that randomly. I think this is a binomial distribution, but calculating a random binomial variable doesn't have a "one shot" closed form, You can get close enough by finding the expected mean and standard deviation and using the erf() function to find a random variable on the normal distribution (This might be less accurate with kill rates close to 0 or 1). Take that number off both the size of that regiment and the total damage left to allocate.
For a binomial distribution, the mean is \$np\$ where \$n\$ is the number of units and \$p\$ is the probability of being killed, the standard deviation is \$\sqrt{np(p-1)}\$. If you can generate a random Gaussian variable r with a mean of 0 and standard deviation of 1, mean+r*sdev should give you what you want.
Now recalculate the remaining proportion of losses, and do the next regiment in the same way. Repeat for all regiments except the last one.
For the last regiment, just take the remaining damage.
It might be a little counter-intuitive, but if your distributions are close to correct and you catch edge cases (such as checking that remaining kill rate always stays between 0 and 1 inclusive), the order that you do this in doesn't mathematically matter - there won't be any bias (although I would go from smallest to largest to best avoid the edge cases).
For your example, you want to take 1000/5500 (proportion 0.1818...), so the mean is 90.909..., the standard deviation is approximately 8.62439. Say you determine that the first regiment takes 85 damage (slightly below average). You now have 915 damage to distribute between the other two regiments, 915/5000 = 0.183. Say the second regiment takes 187 damage (slightly above average). The remaining regiment takes the remaining 728 damage.
Having done all of that, it would be much easier and still reasonably quick to do a simulation (just take damage one at a time and recalculate proportions as you go) unless the regiments get really large.
For bias towards small or large regiments, just tweak the probabilities, but I'm not going to go into that since I see you removed that part of the question.