Though changes to the instruction set do not happen at every release there are normally changes to the class file format - so although generics were implemented by type erasure at Java 5 so did not need an instruction set change new signature information was added to the class file format to describe the type parameters, and annotations were introduced which required further class file format changes.
However, you can have compiler generate lower version bytecode for you. If you have a Java 8 compiler but want Java 1.4 bytecode - no problem, just ask compiler to target 1.4. It will warn you if you use any >1.4 features. Maybe it will even let you use lambdas (maybe not, I'm not sure).
Java is very backwards compatible. That's why it progresses so slowly perhaps.
However, you can use Java 6 compiler to compile Java 6 code to JVM 1.4 bytecode. That's what you are talking about.
I don't think there's any theoretical reason for the bytecode or the bytecode assembler language to need to change. Just like there's no reason lisp and c can't both be compiled to IA32 bytecode, even though lisp has lambdas and c does not.
Rather the issue is going to be at the compilation stage, where support for anonymous methods will need to be added. From my limited knowledge of compilers two ways it could be done are:
* just give the lambda methods a namespace that is unique from the namespace programmers have access to (eg a variable with a space or a tab in its name). Now lambdas will be handled like regular named methods, but the namespace for them will be invisible to the programmer, and the compiler will be modified to have two method namespaces/an expanded namespace for functions.
* Make all methods lambdas and then bind method variables to the lambda methods similar to how atomic/primitive (eg integer, float, chars) and other non-atomic/reference (objects, arrays) variables are bound to their anonymous objects. This is similar to how anonymous objects are handled. An anonymous object is what's returned by constructors, which are then bound to some variable. In this case the compiler needs to support methods that aren't bound to a variable.
That said, it's entirely possible that making changes to the bytecode and the jvm will allow for faster running code, but those changes wouldn't be required out of some theoretical necessity for supporting lambdas.
I was actually thinking at this from a "language evolvability" p.o.v. : if, hypothetically, a language like Python would be bytecode compiled and the bytecode compatible v2 to v3, you could evolve the language syntax much faster without the worry for complicated "transitions": You could then use python 2 libraries in a python 3 program and so on...
I'm in the initial stages of a (not so serious) language design project - a language "designed for accelerated evolution of both syntax and semantics", and I was considering the hypothesis that a "bytecode" compiled language could evolve much faster than either an interpreted or compiled-to-machine-code one.