Can we rent a vehicle prior to visiting Iceland or should we do it
after landing?
Yes, and I would advise you do so as the 'walk up' rates are often higher than 'pre-paid' ones.
What are Iceland's reliable and recommended rental car services for
this purpose?
All of the renters at Keflavik are decent, I think I've rented from them all over the years.
Can international license holders drive in Iceland with an
international driver's license (are there any exceptions)?
I'm a Brit and didn't need to do anything other than show my UK licence, you need to just read the agreement with whoever you're going with - that or call them to ask.
Any recommendations (things to note) from someone who has rented a
vehicle during Iceland's winter?
If you're an experienced ice/snow driver than by all means rent a non-4x4, but I'd still advise it, it can be very treacherous to drive at times and even just the drive from the airport into town is further than a lot of people think, it's on the west side of the island too so gets a bit more of the westerly snow and ice too. The renters may well try to sell you on 'ash insurance', this is quite useful in the summer where ash does settle on the roads and scours off the paint quite quickly, but the more rain/snow there is the less of a problem it it.
Have fun, try to get out of the city too, it's an amazing landscape if the weather permit.