Adapting from here:
http://j-walk.com/ss/excel/tips/tip46.htm
and taking a few lazy shortcuts along the way I got this:

Dim myWordsArray
Dim CurrentRow

Sub GetString()
Dim mySentence As String
mySentence = "Hello have a nice day"
myWordsArray = Split(mySentence, " ")
Dim InString As String
InString = Left("0123456789", UBound(myWordsArray) + 1)
If Len(InString) < 2 Then Exit Sub
If Len(S) >= 8 Then
MsgBox "Too many permutations!"
Exit Sub
Else
ActiveSheet.Columns(1).Clear
CurrentRow = 1
Call GetPermutation("", InString)
End If
End Sub

Sub GetPermutation(x As String, y As String)
' The source of this algorithm is unknown
Dim i As Integer, j As Integer
j = Len(y)
If j < 2 Then
StrVarT = x & y
VarT = ""
For k = 1 To Len(StrVarT)
VarT = VarT & myWordsArray(Val(Mid(StrVarT, k, 1))) & " "
Next k
Cells(CurrentRow, 1) = Application.WorksheetFunction.Trim(VarT)
CurrentRow = CurrentRow + 1
Else
For i = 1 To j
Call GetPermutation(x + Mid(y, i, 1), _
Left(y, i - 1) + Right(y, j - i))
Next
End If
End Sub

Paste the above into a module, making sure the top two lines (Dim
statements) are at the top of the module in the declarations area, and
run GetString. It clears anything in the column A of the active sheet
so be careful.