I tried to power on the thing with the lcd unplugged and then plugging it back: everything worked fine. So the problem clearly is the built in regulator,
Wait what? You unplugged the LCD and that clearly indicates a problem with the regulator? That seems like a tenuous cause-effect relationship.
it can`t take the current surge requested by the lcd (wich is absolutely necessary in this project) on startup.
If this were actually true, then you have much larger problems. Most LCD backlights are a couple of LEDs. Not exactly a huge "current surge" kind of device, when implemented properly.
I was thinking to some sort of capacitor on the rest pin of the ardu to reset it a coople of 100/ths of seconds after initial power on but sounds a very rough solution to me
I'm not really certain what this would accomplish. The 5V reg, 3V3 reg, and 8U2 consume the same amount of power is RESET is asserted or not, since they don't pay attention to the RESET signal.
You used the phrase "everything worked fine". If this is true and you verified "everything" works fine, then the problem seems to point to the device you removed. It sounds more like a code initialization problem than a current issue.
A couple of quick measurements with a multimeter might be in order to prove it. (Amount of current drawn with and without this, apparently massive, LCD.)