Four is the magic number

Bash + common utilities (including bsd-games), 123 - 30 = 93 bytes

for((n=$1;n-4;n=m)){
m=`number -l -- $n|sed 's/nus/&&/;s/\W//g'`
s+="$n is $[m=${#m}] and "
}
echo $s 4 is the magic number

Luckily the output from the bsd-games number utility is almost exactly what we need. Output numbers are all written numerically and not in words as per the 8th bullet point:

$ ./4magic.sh 131072
131072 is 37 and 37 is 11 and 11 is 6 and 6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
$ ./4magic.sh -4
-4 is 12 and 12 is 6 and 6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
$ 

C, 263 261 bytes - 180 = 81

char*i="jmmonnmoonmpprrqqsrrjjddeeecdd",x;f(n,c){return!n?n:n<0?f(-n,8):n<100?c+i[n<20?n:n%10]-i[20+n/10]:f(n/1000,8)+f(n/100%10,7)+f(n/100%10,0)+c;}main(int c,char**v){for(c=atoi(*++v);c-4;c=x)printf("%d is %d and ",c,x=c?f(c,0)):4;puts("4 is the magic number");}

Inspired by the answer from Cole Cameron. I thought I might be able to do better without the macro definition. Although I eventually managed, it did take some squeezing to achieve!

It requires a host character set with consecutive letters (so ASCII is okay, but EBCDIC won't work). That's for the pair of lookup tables. I chose j as the zero character, and took advantage of needing two lookups, so I could subtract one from the other rather than having to subtract my zero from both.

Commented version:

char*i=
    "jmmonnmoon"                /* 0 to 9 */
    "mpprrqqsrr"                /* 10 to 19 */
    "jjddeeecdd";               /* tens */
char x;                /* current letter count */

f(n,c){
return
    !n?n                        /* zero - return 0 (ignore c) */
    :n<0?f(-n,8)                /* negative n (only reached if c==0) */
    :n<100?c+i[n<20?n:n%10]-i[20+n/10] /* lookup tables */
    :
      f(n/1000,8)               /* thousand */
    + f(n/100%10,7)             /* hundred */
    + f(n%100,0)                /* rest */
    + c;                        /* carry-in */
}
main(int c, char**v)
{
    for(c=atoi(*++v);c-4;c=x)
        printf("%d is %d and ",c,x=c?f(c,0):4);
    puts("4 is the magic number");
}

There's an obvious extension to support millions, by replacing f(n/1000,8) with f(n/1000000,7)+f(n/1000%1000,8).

Test output

0 is 4 and 4 is the magic number
1 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
2 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
3 is 5 and 5 is 4 and 4 is the magic number
4 is the magic number
5 is 4 and 4 is the magic number
6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
7 is 5 and 5 is 4 and 4 is the magic number
8 is 5 and 5 is 4 and 4 is the magic number
9 is 4 and 4 is the magic number
10 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
17 is 9 and 9 is 4 and 4 is the magic number
100 is 10 and 10 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
142 is 18 and 18 is 8 and 8 is 5 and 5 is 4 and 4 is the magic number
1000 is 11 and 11 is 6 and 6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
1642 is 29 and 29 is 10 and 10 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
70000 is 15 and 15 is 7 and 7 is 5 and 5 is 4 and 4 is the magic number
131072 is 37 and 37 is 11 and 11 is 6 and 6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
999999 is 50 and 50 is 5 and 5 is 4 and 4 is the magic number

Swift 2, 408 419 - 30 = 389 Bytes

I would be able to get rid of 176 bytes if it Swift wasn't so verbose with regular expressions (removing hyphens and spaces) *glares at Apple*

func c(var s:Int)->String{var r="";while(s != 4){r+="\(s)";let f=NSNumberFormatter();f.numberStyle=NSNumberFormatterStyle.SpellOutStyle;let v=f.stringFromNumber(s)!;s=v.stringByReplacingOccurrencesOfString("[- ]",withString:"",options:NSStringCompareOptions.RegularExpressionSearch,range:Range<String.Index>(start:v.startIndex,end:v.endIndex)).utf8.count+(s<0 ?3:0);r+=" is \(s) and "};return r+"4 is the magic number"}

This can be tested on swiftstub.com, here

I ran a little for loop, and it turns out that 100003 is the number between 0 and 999999 has the longest string result, which has 6 iterations, and is

100003 is 23 and 23 is 11 and 11 is 6 and 6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number

Ungolfed

func a(var s: Int) -> String{
    var r = ""
    while(s != 4){
        r+="\(s)"
        
        let f = NSNumberFormatter()
        f.numberStyle = NSNumberFormatterStyle.SpellOutStyle
        let v = f.stringFromNumber(s)!
        s = v.stringByReplacingOccurrencesOfString(
            "[- ]",
            withString: "",
            options: NSStringCompareOptions.RegularExpressionSearch,
            range: Range<String.Index>(start: v.startIndex, end: v.endIndex)
        ).utf8.count + (s < 0 ? 3 : 0)
        
        r+=" is \(s) and "
    }
    return r+"4 is the magic number"
}