What would be the best glue for the job? I'm not sure if regular wood glue would be enough.
If by 'regular wood glue' you mean PVA-type glues (either white or yellow) then yes that can work. PVA can be used cold (as normal, positioning when wet) or hot1 in veneering.
Epoxy might be suitable. The porosity of the wood used and the thickness of the veneers are important here as any glue squeezed out onto the surface2 will cause problems later.
You might also consider using liquid hide glue (AKA room-temperature hide glues, that don't need to be kept warm). Note: although it's traditional you don't have to texture the substrate in advance when using hide glue for veneer work. This is old thinking and testing has shown it's not necessary and actually can be counterproductive.
Would some kind of contact adhesive work?
It could I suppose, but it's not the ideal choice for a couple of reason. In the long term I'd worry about adhesion on small pieces, but there are two issues I see straight away that I think rule it out immediately in terms of what's practical.
The first is the glue needs to be spread on both pieces, left to dry a little ('tack up') so it would slow the process down a fair bit. Then you basically have one shot only to get something positioned exactly right. With the other suggestions above you have at least a little wiggle room (literally and metaphorically) which could be a huge boon. Epoxy in particular would give you a minute or two and up to an hour to fine-tune positioning of every piece, and if you use PVA as a thermosetting adhesive you have essentially unlimited repositioning time.
For some of the bigger pieces I'm thinking of using hot-melt glue. Is there a way to do fine work with a hot melt glue gun?
Fine work in general, I'm sure there is but I doubt it's really possible to use it for veneer work (how to spread it thinly and evenly, and keeping it hot enough to stick?) and cleaning up excess could prove problematical.
1 You coat both the back of the veneer and the substrate, let the glue dry, then you iron the veneer (protecting the face, e.g. with brown paper) which melds the two layers of dried adhesive.
2 Glue can come through the wood, not just around the edges.