Нет способа заставить этикетку обновиться, которая действительно будет работать в вашем случае. Если пользовательский интерфейс заблокирован, он не будет обновляться. По сути, когда вы на самом деле дойдете до точки, где вы обновляете текст метки, он будет отображаться в WPF. Единственное возможное исключение, о котором я могу подумать, это если вы используете элемент управления не-WPF, но даже тогда он должен работать.
Мое предложение было бы обновить метку перед выполнением первого действия (даже до инициализации переменных, поскольку это может быть там, где на самом деле проблема). Вот пример псевдокода того, что я имею в виду (на случай, если мне неясно):
private void KickOffProcess()
{
label1.Text = "Processing ..."; //This is where you need to move the label update code
AsyncCall();
}