Surprisingly, in order to upgrade the level of politeness (or formality), we can only append です to the negative of the informal form.
This is an interesting observation, as it is true that appending "です" to the negative forms is common, while the same for the positive forms is highly unusual.
The issue you observed comes from how い-adjectives are made polite in Japanese, by appending "です" to them. For sounding very similar, and holding some same grammatical properties as い-adjectives, ない has naturally adopted the same grammatical rules; 痛い → 痛かった - ない → なかった, 痛いです → 痛かったです - ないです → なかったです.
Nonetheless, the foolproof way to "upgrade the level of polieteness" is, as brought up in your post, to use the "ます"-forms. What "ないです" actually is, is a colloquial version of the polite form (which exists both for present and past tenses), where "です" is simply appended to the verb.
Does 食べないです (and 食べなかったです) have the same level of politeness as 食べません (and 食べませんでした) has?
The level of politeness is the same, however, the main difference comes from the fact that "ないです" is new and colloquial. Hence, you won't find it as much in formal dialogue, as you would in informal dialogue.
It can also be argued that "ないです" is a softer expression than "ません", although personally, I find it easy to make either expression sound soft, or hard, depending on tone of voice.
Some might also argue that "ないです" not only is a new colloquial expression, but grammatically ill-advised.
Why 食べるです and 食べたです are not allowed?
They are not in use, most likely because they do not share the similarities with い-adjectives. It is, however, possible to append "っす" (see: What does っす at the end of a sentence mean?).
