Запятая может ставиться при интонационном распадении союза на две части.
Слова "тем не менее" не используются как вводные.
ТЕМ НЕ МЕНЕЕ, частица и союз
1. Частица (часто в сочетании с противительными союзами «а», «но», а также в предложениях с союзами «хотя», «несмотря на то что», «пусть» и др.). Не требует постановки знаков препинания.
Мюллер долго наблюдал за тем, как медленно, еле заметно, но тем не менее неуклонно лучи двигались по комнате. Ю. Семенов, Экспансия-I. Несмотря на то, что Ягозин был кровным детищем Петербурга… он весь тем не менее состоял из одной быстроты и юркости. Д. Григорович, Карьерист.
2. Союз (между частями сложносочиненного предложения). То же, что «но, однако».
…Это были все-таки карты, несколько захватанные, затертые пальцами по краям, тем не менее невозможно было представить, что в них играли за столом... Ю. Бондарев, Горячий снег.
Валяющейся на полу – причастный оборот, но запятая не ставится, т. к. оборот связан по смыслу со сказуемым (смысл высказывания заключается не в том, что он обнаружил шинель, а в том, что шинель валялась на полу).
Форма винительного падежа (Он не совершал преступление) используется, если речь идет о конкретном преступлении. Форма родительного падежа (Он не совершал преступления) — если речь идет о каком-либо преступлении вообще.
Запятая нужна. Д. Э. Розенталь пишет: «Не является объединяющим элементом противительный союз, после которого или перед которым находятся два соединенных союзом и простых предложения, поэтому запятая перед и ставится: Ибрагим был бы очень рад избавиться, но ассамблея была дело должностное, и государь строго требовал присутствия своих приближенных...»
Первый вариант предпочтителен, второй допустим.
Верно: Он и она стояли на мосту.
Здесь пишется частица ни.
