I was starting to wonder whether you could get back to the drop off or is it behind security but then I realized something: you won't be able to add it during the recheck because last I've done this (although not at EWR but I suspect it's the same) it was not like a full service station complete with baggage tag printers just a simple drop off. Thinking more, it is one drop off for every airline so there's really no way to get your thing into the airline system. That would require a replication of the check-in floor. As your luggage is tagged to the end already, you can simply drop it off here but untagged baggage just can't happen.
As for adding more luggage I can't imagine why the airline wouldn't accept it if you pay the extra luggage fee. My train of thought is -- if you'd need to gate check something then you can so I am sure they'll be happy with not messing with a gate check.