Do Sharepoint Workflows have to 'block' the UI whilst processing?

'Block' in the sense that the user is shown the "Workflow is starting" page while the workflow runs.

Is there a model for 'asynchronous' workflows where a potential long running workflow trundles away reporting its progress to the history list and maybe informing the originator that the process has finished via email.

History list and email I can do - I cant see how to set up a 'asynchronous' workflow

A sharepoint workflow runs on the thread starting it until it comes to an activity waiting for something to happen.
It'll then continue in the SPTimer Service

So the easiest way to create an 'asynchronous' workflow it to insert a Delay activity (Pause for Duration if using SPD) as early as possible.

P.S. Make sure you got the 'Infrastructure Update' or SP2 installed otherwise the workflow may not resume