The solution suggested by Juho applies to any problem where you can generate an object that trivially has the property you're interested in and then modify it in a way that maintains that property:
For the problem in the question, start with a path and randomly add edges obeying the degree conditions.
To generate a graph with a $k$-clique, start with a $k$-clique, then add the rest of the vertices, then add edges at random.
To generate $k$-colourable graphs, start with no edges, randomly choose the colour of each vertex and then randomly add edges between different coloured vertices.
To generate satisfiable 3CNF formulas, start by picking a truth assignment for the variables and then add random clauses that have at least one true literal.
To generate unsatisfiable 3CNF formulas, start with something simple and unsatisfiable and add random clauses to it.
If you don't care about the distribution of the instances you generate, these methods work fine. If you do care about the distribution, things get trickier. If you want a uniform or near-uniform distribution (i.e., each Hamiltonian graph on $5n$ vertices is generated with [roughly] equal probability), you should look into Fully Polynomial Almost Uniform Samplers (FPAUS). These typically use Markov chain Monte Carlo and the method for your problem would probably be to start with a path and then randomly add and remove the extra edges enough times that the process converges to the right distribution (you'd have to check this actuall works).
Another thing to be aware of is that instances generated in this way might be easy to solve if you knowsomething about how they were generated. For example, in the clique example I gave, if you just add each the non-clique edge independently with probability $p$ for some $p$, it's very likely that your clique is just the $k$ vertices of highest degree.
