I'm actually impressed by the level of detail provided in the rejections. There's nothing worse than getting a rejection that does not clearly state the reason for the rejection and a path to resolution. Apple and especially Google are notoriously bad about this.
You definitely can get an Alexa skill off the ground without using Lambda, but there are a lot of little details with their authentication to work out. I'd highly recommend one of the libraries that are out there:
This article sums up my recent experience trying to get a skill published. It was slightly frustrating to receive multiple rejection emails, but at least the responses were detailed and helpful.
While building some skills for fun, I also made some gulp tasks for locally testing skills and deploying the code to your lambda. https://github.com/tmcleroy/alexa-skills
I built a similar app for Chicago's CTA trains, called CTA Tracker. There seem to be train tracker apps for most major cities, since they're easy to implement and legitimately useful.
Why would you be scared? The keyword(s) is processed locally, and it only sends the request following the keyword over the wire. If they tried anything fishy, such as sending everything it hears over the wire, then they would be outed within a day.