What you more than likely are having issue because of the fact the wood is old. The outer-side might have been coated with something back when it was made to preserve the wine. Not sure for certain but it makes some sense to me. But these are the steps to making this barrel look great again.
1) Since the wood is dark and will not stain you need to sand* the outer surface until the wood looks darn near new. Start with a low grit, like 80 (I might do 40 depending on how bad it is). And work up to 120/150. And if you want 180/220.
2) Go ahead and stain. Now that the old stuff is removed go ahead and start staining. I take a old shirt and cut it into pieces and apply 1-2 coats. There are other methods but that is my favorite.
3) A great way of protecting the wood (and stain) from water and other damage would be a protective coat like polyurethane (I use it all the time). I would use Oil-based because it is water resistant (oil does not mix with water) but will give a amber tint to the wood/stain. There is also water-based. I think I am going to make a quick pro con of the too off the top of my head.
Oil-based - Good
Strong, 3 coats, lasts long
Oil-based - Bad
Amber tint, fumes are smelly
Water-based - Good
Quick drying, easy clean up, little tinting
Water-based - bad
5 coats, Don't think it is water-resistant, not as strong
There are more to the polyurethane world but that should give a idea as to what to expect.
I really do not think it could be any simpler. But of course if I am off say something in the comments and I will gladly correct myself. I hope this helps you. Good luck on your project!
*If you do not have a sander I would get one. A orbital sander is the a good sander to start with. Removes more than a 1/4 sheet sander but less than a belt sander. So Unless you like hand sanding, any cheap sander I would get to save time.