Just glancing at it, this:

    template<class BidirIt>
    void weave(BidirIt first, BidirIt last) {
        if ((last - first) < 3) {
            return;
        }

...jumped out--although the template parameter seems to imply that you want this to work for bidirectional iterators, the subtraction will only work for a random access iterator. To work for bidirectional iterators, you'll want to use `std::distance` instead.

Although it's only in the test code:

    std::ostream& operator<<(std::ostream& out, const std::vector<int>& v) {
        if (v.begin() == v.end()) {
            return out << "{}";
        }

...I'd prefer `if (v.empty()) {`

As far as the algorithm goes, yes, there's better. In particular, it looks like your current algorithm is \$O(N^2)\$, but it's possible to do the job in \$O(N)\$ (as you probably expected).

The first step would be to reverse the entire second half of your input. From there you can use an [in-place shuffle](http://arxiv.org/pdf/0805.1598v1.pdf) algorithm. Also see an old [answer on SO](http://stackoverflow.com/a/1778251/179910).