How can I change the language for dictation on the fly? With English not being my first language, I usually need support for at least two languages when using features like auto-correct and dictation.

Is it possible to toggle the language which is used for dictation via a shortcut?

As of now, I always have to manually navigate through the menus in the System Preferences which if far from convenient. I've tried to see if there are any pre-defined actions in Automator, but found none.
You could either edit property lists that store the setting and reopen the DictationIM process:

#!/bin/bash

k="com.apple.speech.recognition.AppleSpeechRecognition.prefs DictationIMLocaleIdentifier"
if [[ "$(defaults read $k)" == en-US ]]; then
  defaults write $k fr-FR
  defaults write com.apple.assistant "Session Language" fr-FR
else
  defaults write $k en-US 
  defaults write com.apple.assistant "Session Language" en-US
fi
killall -HUP DictationIM


Or use UI scripting:

tell application "System Preferences"
    reveal anchor "Dictation" of pane "com.apple.preference.speech"
end tell
tell application "System Events" to tell process "System Preferences"
    tell pop up button 1 of tab group 1 of window 1
        click
        if value is "English (United States)" then
            click menu item "French" of menu 1
        else
            click menu item "English (United States)" of menu 1
        end if
    end tell
end tell
quit application "System Preferences"


Both scripts are copied from my answer to How to use applescript to toggle the language setting of new dictation tool (10.8) - Stack Overflow.