What must be the minimum input voltage of a series regulator?
This is a very basic regulator, and it doesn't regulate well. The output voltage depends on how constant the zener's voltage and the base-emitter voltage. First the transistor:  



This graph shows that base-emitter voltage can vary by more than 300 mV between 1 mA and 1 A load. Above 20 mA you have more than the 0.7 V drop you assumed.  

Also a zener voltage is not as constant as you may think. If the load decreases zener current will rise, and with it zener voltage. 

A better circuit uses feedback from the actual output voltage, so that B-E junction is compensated:  



This is for a 13.6 V supply. D1, R1 and R2 determine output voltage: 

\$ \mathrm{V_{OUT} = \dfrac{R1 + R2}{R2} (V_Z + 0.7 V)}\$  

So this also depends on a B-E junction voltage, but the current variation in Q1 will be far less than in Q2.

edit
A few people commented on this schematic. I just wanted to show how you can create a better (though far from perfect yet) regulator if you take your feedback from the output voltage. I know you need other components for 3.3 V out. You can replace D1 by a 1N4148, or delete it altogether. You'll have 1.4 V resp. 0.7 V at the point marked "Feedback". Choose R1 and R2 accordingly.

Now your actual question. Let's start by decreasing R1 to 100 \$\Omega\$, 10 k\$\Omega\$ is too high. The datasheet specifies \$H_{FE}\$ for a minimum \$V_{CE}\$ of 2 V, so we'll need at least 5.3 V in if we want to rely on that \$H_{FE}\$. Then the current through R1 is 14 mA (with the 10 k\$\Omega\$ it would only have been 140 \$\mu\$A).
If 10 mA of that goes to the base then we can supply 250 mA to the load. That's not much, but like most power transistors the BD135 has a low \$H_{FE}\$, 25 typical at 500 mA collector current. Higher input voltage will give you a higher base + zener current.