First thing first: was the O2 sensor you put in a known good and correct one from Chase's sensor list on OpenGK, or was it an Alibaba Special?
If your sensors are good, it gets hairy, because random misfires can be caused by...
- Bad gas
- Worn/clogged fuel injectors
- Bad fuel regulator
- Worn fuel pump
- Bad/clogged O2 sensor
- Bad MAF sensor
- Bad IAT sensor
- Bad ECT sensor
- Worn plugs
- Worn coil pack
- Damaged/loose/corroded wiring
- Corroded ground points
- Loose knock sensor
- Loose position sensor
- Worn timing belt
- Clogged PCV
- Planetary alignment
- Swamp gas
- Weather balloon
Make sure you're up to date on maintenance, get good gas and put a bottle of injector cleaner in the tank while you do so.
Then, look for anomalies. Get live data over OBD-II and make sure you're getting a clean MAF and TPS signal (no weird dips or spikes).
Check long term fuel trim and make sure it's similar for both banks and in the +/- 8% range. Values outside that could indicate bad MAF, IAT, TPS, IACV, weak fuel pump, bad pressure regulator, bad O2 sensor, basically anything fuel related.
Check for erratic timing advance, this could indicate bad spark.
Basically get a better picture of what you're working with.