The word "unless" is a conjunction that joins two clauses together. The phrase "having been trained very young" isn't a clause, so it cannot come after "unless", so the second sentence is ungrammatical.
The first sentence is correct because the word "trained" in that context is understood to be a reduced form of "they were trained", which is a clause, so it can follow "unless".
If you want to use "having been trained", "having" is a gerund, which is a noun, so you need a preposition in the place of "unless". "Without" is a preposition with roughly the same meaning:
No one can walk the wire without a bit of fear without having been trained very young.
Repeating "without" twice in the same sentence is poor style, but the grammar and meaning are good.