High Voltage Multilayer PCB
Yes you should be fine as long as you take care with the design

The IPC-2221 provides typical electrical properties for common materials (FR4, Polyimide etc... ) &amp; as you stated, the electrical strength is around 39kV/mm. 

A copper clad laminate would therefore, in theory, be perfectly capable of withstanding 600V.

That said ... There are a few consideration and not just in the x-y plane with regards to trace separation (again IPC-2221) 


Pad &amp; track corner design. Round them off to mitigate buildup of charge &amp; maximise the corona inception voltage. This is a must for medium voltages &amp; not so much with the low voltages of 600V, unless altitude is a real consideration. 
FR4 absorbs moisture quite readily &amp; this reduces the electric strength capability.  
Prepreg voiding (and also laminations) While in theory the electric strength is 39kV/mm, in practice manufacturing can result in localised areas that do not meet this. 


My personal recommendation would be to separate the high voltage via the prepreg instead of the laminate. Double-prepreg the stackup as well to mitigate instance of voiding (what is the probability that two voidings occurrences align? ).