Especially for appliques, grain does not matter when cutting (especially when using scraps). For turned applique, the edges turn better when they are bias anyway.
You could certainly do them via needle turn applique by hand without adhesive. Not something I would like to do (hand problems make hand work too difficult for me).
Whenever doing machine applique, I *always* heavily starch the background squares so I don't have to use a stabilizer underneath. This prevents tunneling (if using satin stitch) and just generally prevents the background fabric from shifting while I stitch. My method is to mix a 1:1 solution of liquid Sta-Flo laundry starch and water, "paint" the solution onto yardage using a large wall painting brush until fabric is saturated, toss in dryer, then iron with steam. Only after that do I cut the background squares, and then I usually cut them 1" bigger than needed and cut them down to correct size after the applique is done (to ensure precision size).
For machine applique, unless you want to do raw edge applique, I think using a fusible is best. If you don't want added heaviness to the applique, then use Misty Fuse. Too many pins get in the way when doing machine applique and, if you are like me, you will stick yourself one too many times!