I want 2 of my devices to communicate with UART. I do not have any timing requirements
Does that mean I can choose any baudrate as long as receiver's and transmitter's baudrates match and it is in the available range of my chip?
I'm afraid the answer is not that simple. Your device's UART baud rate generator must be able to generate the said baud rate, generally User Manual/Reference Manual contain a formula to drive possible baud rate that can be achieved.
Are both the devices on same PCB; if not then I would recommend you introduce a level translator like MAX3232 and transmit/receive signal in RS-232 level to avoid communication problems.
Also remember at high speed the track/wire capacitance and inductance also come into play.
Do frequency of chip and baudrate of the UART need to be same? I have read that frequency of the chip needs to be 16 times higher than the baudrate of UART. But in some other places people say that it is fine as long as your MCU has a higher clock frequency than the baudrate. (i.e: for 9600 kbps, MCU needs to be higher than 9.6 khz.
What micro-controller are you using? Modern micro-controller operate at much higher frequencies than typical baud rate. Many modern high-performance micro-controller work in hundred's of MHz. Every modern micro-controller tends to have a clock divider for peripheral and further a baud rate generator to achieve proper baud rate. The answer to this question depends on what MCU you are using. For fairly modern MCU you neither require the frequency of chip and baud rate of the UART need to be same nor that frequency of the chip needs be 16 times higher than the baud rate of UART.
Can I use different frequencies for two devices? (for example 20 MHz for receiver and 8 MHz for transmitter.
Yes, you can use different frequencies for two devices. Just make sure their baud rate along with other parameters like parity, data length, etc.