The second one is correct.
-The accused denied ... in the vicinity of the murder scene.
-to have ever been
-ever having been
For the gap, which one is more suitable? I did not figure out, especially grammatically.
Than you in advance..
"Deny" is usually followed by an "-ing" verb form, not a full infinitive.