Question 1: Is it possible to have serial output (for midi flow) with an Attiny85?
The ATTiny85 can use NewSoftSerial/SoftwareSerial to do serial communication.
Question 2: Is it possible to operate at 31250 baudrate (midi) with the internal 8Mhz clock, or would I absolutely need an external 16Mhz xtal?
Yes. The 3.3V Arduinos operate at 8MHz with no serial communication issues at any speed.