Running barebones ATMEGA328P on 3.7 V battery
As usual, all this info is in the data sheet, but it can be hard to find for the inexperienced.  In this case, it is Figure 28.2, DC Electrical Characteristics, and you need to find \$V_{OH}\$, the output high voltage.

Note that this is substantially lower than \$V_{CC}\$, and can vary under different conditions. It looks like assuming at least a diode drop is in order. If you need it to be \$V_{CC}\$ you should look to see if you can configure the ports to be open collector.  Otherwise, the high output should be more than enough to be interpreted as a high for most logic families your devices are likely to be communicating with.
Your UART output will be at \$V_{OH}\$
Your last question is a little tougher

The absolute maximum voltage will be \$V_{CC} + 0.5\$.  Sometimes, you can set things up so the PROGRAMMER provides the \$V_{CC}\$, and if you can do this, you won't have any trouble.  If you can't do this, and you want to be sure your chip will function as specced, you'll need to somehow clamp the inputs if your programmer works at 5V.  If your programmer works at 3.3V, you'll be fine, as anything above 0.6V on the digital inputs will be read as high.