The spy doesn't need to establish surveillance in order to do advanced actions (see Edit, I misread your post). Your spies do it as well (quite annoying actually, when people ask you to stop spying even before your agent is set up). And I think, advanced actions are separate from tech/work steals, so they may occur at the same turn. So, you are able to do this with your spies, too (whereas in my opinion, the advanced actions thing is not logical, but that's another point).
Edit: Also, keep in mind that there's a statecraft policy that gives a spy before anybody is in Renaissance. And I misread your post, sorry, tech steal should indeed not be possible before the spy is established.