Handling uncertainties is one of the most important challenges in nonlinear model predictive control (NMPC). While several robust NMPC methods have been recently presented, their implementation on embedded systems is usually difficult due to the necessary conservative assumptions or because of the required computational complexity. In this work, we use a complex robust NMPC approach to generate data pairs that are used to learn an approximate robust controller which is robust to model uncertainties. We propose to use deep neural networks to learn the approximate controller based on recent results that prove the powerful representation capabilities of such networks over traditional shallow ones. The approximate controller, which just requires the simple forward evaluation of neural network, can be easily combined with an Extended Kalman Filter to obtain an efficient embedded implementation of an output-feedback robust NMPC scheme. We propose a statistical verification strategy to compute backoffs that lead to the satisfaction of important constraints despite the presence of estimation, measurement and approximation errors. The potential of the approach is illustrated with numerical results for the embedded robust control of a towing kite.