4.x is primarily designed for the Flyer - not sure you'll get much benefit out of it with only the Toaster. It might be worth going to 3.5, though.
I recently finished building a dedicated Toaster box. In the interests of maximum compatibility / fewest conflicts, I installed the Toaster software over a base install of AmigaOS3.1 - with nothing else installed except AsimCDFS and Envoy. If I want to do non-Toaster things, I created a separate bootable partition for regular Amiga stuff.
The Toaster 4000 manual doesn't even endorse 3.1, except on 4000Ts. Since OS3.9 messes around with memory and ROM updates, it seems like it could cause conflicts. The Toaster eats loads of Chip RAM, so if there's any missing there might be trouble.