While Brandon's example about Cake shows a negative verb can be used with 初めて, I feel that in general that is an exception. I searched online and found a few other examples where a negative verb was used after 初めて:
Here, this means that this was the first year (after 20 years) where something wasn't done.
This indicates that there is some jobs which you'll be doing for the first time.
This indicates that the person was able to sleep for the first time without doing something.
As you can see, in all of these cases there is some context where it makes sense to use a negative verb after はじめて. I can't think of any case where the simple form "初めて" + (negative of verb) would make sense, except Brandon's example with "食べたくならなかった". For example, this sentence seems strange to me.
I think saying either of the below would be more natural.
Regarding the second question, I agree with what Brandon said, but here is one other way to express that.