Tallest tower from a set of digits
Python 2 - 326

Runs easily under the time limit for all the examples given, though I did sacrifice some efficiency for size, which would probably be noticeable given much larger inputs. Now that I think about it though, since only single digits numbers are allowed the largest possible tower may not be very big, and I wonder what the maximum is.

def S(u,c=0,w=[]):
 for(s,e)in[(len(w),lambda w,i:w[i]),(len(w)+1,lambda w,i:.5*sum(([0]+w+[0])[i:i+2]))]:
    m=u[:];l=[-1]*s
    for n in u:
     for i in range(s):
        if 0&gt;l[i]and n&gt;=e(w,i):m.remove(n);l[i]=n;break
    if([]==l or-1in l)==0:
     for r in S(m,c+1,[1+e(w,i)for i in range(s)]):yield r
 yield c
print max(S(sorted(input())))