Probably the most efficient way is a case
statement:
select (case left(col, 2)
when '01' then 'January '
when '02' then 'Feburary '
. . .
when '12' then 'December '
end) + right(col, 2)
This has the fewest calls to functions. There are more concise ways to do this, such as:
select datename(month, cast('2013' + col as datetime)) + right(col, 2)
Of course, to get the most efficient, you should set up a test in your environment on something like 1 million records and actually test the different timings.
For instance, it might be fastest to have a reference table with 366 entries, one for each day, and use a join
to do the conversion.